The unusual complex lithospheric structure of Madagascar is a product of a number of important geological events, including: the Pan-African Orogeny, episodes of Late Cenozoic intraplate volcanism and several phases of deformation and metamorphism. Despite this rich history, its detailed crustal structure remains largely underexplored. Here, we take advantage of the recently obtained data set of the RHUM-RUM (Réunion Hotspot and Upper Mantle–Réunions Unterer Mantel) seismological experiment, in addition to previously available data sets to generate the first Rayleigh wave group velocity maps across the entire island at periods between 5 and 30 s using the ambient noise tomography technique. Prior to preliminary data preparation, data from Ocean Bottom Seismometers are cleaned of compliance and tilt noise. Cross-correlating noise records yielded over 1900 Rayleigh wave cross-correlation functions from which group velocities were measured to perform surface wave tomography. Dispersion curves extracted from group velocity tomographic maps are inverted to compute a 3-D shear velocity model of the region. Our velocity maps have shown relative improvement in imaging the three sedimentary basins in the western third of the island compared to those of previous studies. The Morondava basin southwest of the island is the broadest and contains the thickest sedimentary rocks while the Antsirinana basin at the northern tip is narrowest and thinnest. The lithosphere beneath the island is characterized by a heterogeneous crust which appears thickest at the centre but thins away towards the margins. A combined effect of uneven erosion of the crust and rifting accommodates our observations along the east coast. Average 1-D shear velocity models in six different tectonic units, support the causes of low velocity zones observed in the west coast of the island and reveal an intermediate-to-felsic Precambrian upper and middle crust consistent with findings of previous seismic studies. Our findings, especially at short periods provide new constraints on shallow crustal structure of the main island region.