In this work, multibeam echosounder (MBES) and dual frequency sidescan sonar (SSS) data are combined to map the shallow (5–100 m) benthic habitats of the National Marine Park of Zakynthos (NMPZ), Greece, a Marine Protected Area (MPA). NMPZ hosts extensive prairies of the protected Mediterranean phanerogams Posidonia oceanica and Cymodocea nodosa, as well as reefs and sandbanks. Seafloor characterization is achieved using the multi-frequency acoustic backscatter of: (a) the two simultaneous frequencies of the SSS (100 and 400 kHz) and (b) the MBES (180 kHz), as well as the MBES bathymetry. Overall, these high-resolution datasets cover an area of 84 km2 with ground coverage varying from 50% to 100%. Image texture, terrain and backscatter angular response analyses are applied to the above, to extract a range of statistical features. Those have different spatial densities and so they are combined through an object-based approach based on the full-coverage 100-kHz SSS mosaic. Supervised classification is applied to data models composed of operationally meaningful combinations between the above features, reflecting single-sonar or multi-sonar mapping scenarios. Classification results are validated against a detailed expert interpretation habitat map making use of extensive ground-truth data. The relative gain of one system or one feature extraction method or another are thoroughly examined. The frequency-dependent separation of benthic habitats showcases the potentials of multi-frequency backscatter and bathymetry from different sonars, improving evidence-based interpretations of shallow benthic habitats.