Reliable marine benthic habitat maps at regional and national scales are needed to enable the move towards the sustainable management of marine environmental resources. Due to the paucity of adequate biological data and the prohibitive cost of directly sampling benthic biota over large areas, the most effective means of developing broad-scale benthic habitat maps is to use commonly available marine physical data. A new robust method of mapping marine benthic habitats at this scale was developed based on a stratified approach to habitat classification. This approach explicitly uses knowledge of marine benthic ecology to determine an appropriate number of stratification levels, to choose the most suitable environmental variables for each level, and to select ecologically significant boundary conditions (i.e. threshold values) for each variable. Three stratification levels, with nine environmental variables, were created using a spatial segmentation approach. Each level represents major environmental processes and characteristics of the Australian marine benthic environment. The finest scale of benthic habitat was defined by seafloor physical properties of topography, sediment grain size, and seabed shear stress. The intermediate scale was defined by water-column nutrient parameters and bottom water temperature. The broadest scale was defined by a seabed insolation parameter derived from depth data. The classifications of the three stratified levels were implemented using an object-based fuzzy classification technique that recognises that habitats are largely homogenous spatial regions, and transitions between habitats are often gradual. Classification reliability was indicated in confidence maps obtained from the fuzzy classification. Physical habitat diversity was evaluated for the final benthic habitat map that combines the three classifications. The final benthic habitat map identifies the structurally complex continental shelf break as an area of relatively high habitat diversity. Other extensive areas with a high diversity of habitats include the central and southern Great Barrier Reef and adjacent Coral Sea deep-water platforms, the outer shelf and slope of the Great Australian Blight, and extensive areas of shelf and deep water seabed on the south-western and north-western margins. These areas match well with the distribution of large-scale high-relief geomorphic features (e.g., reefs, ridges, seamounts, valleys, and canyons), likely reflecting the strong influence of bedrock outcrops and reefs on habitat diversity. Overall, the new classification method is relatively easily implemented and updated to include new knowledge and data, and can be applied at spatial scales that are useful for effective management of marine resources at various levels of government.