The seabed of northern Norway was explored using video and multibeam surveys to assess the distribution of megafauna and examine associations of benthic organisms to their physical environment. The study area was initially divided into ten marine landscapes based on seabed morphology and general water mass distribution. In total 195 taxa were observed during video recordings. The highest number of taxa was found within fjord/ coast and upper slope landscapes. Multivariate statistical methods were used to relate bottom environment and taxonomic composition and in order to find the relation between faunal groups and landscapes. Detrended Correspondence Analysis indicated four groups of video transects. The most important environmental factors influencing the groupings were depth, and the frequency of occurrence of mud along the transects. Video transects from canyons and the deep slope formed a distinct group based on faunal composition. The three other groups consisted of transects from banks, fans in outer trough areas, and upper slope/slope terraces respectively. Based on the groups defined by DCA a new set of five landscape classes could be defined. The results indicate that broad-scale topographic features and general hydrography are of relevance for the distribution and composition of megafauna. However to be able to define finer-scaled units of “nature types” more factors (quantitative substrate composition, current regime, etc) must be taken into account, and detailed analyses of the video records must be performed.