The present study reports total mercury (THg) and methylmercury (MeHg) concentrations in 32 different lean fish species from the Western Mediterranean Sea, with a special focus on the Balearic Islands. The concentrations of THg ranged between 0.05 mg/kg ww and 3.1 mg/kg ww (mean 0.41 mg/kg ww). A considerable number of the most frequently fish species consumed by the Spanish population exceed the maximum levels proposed by the European legislation when they originate from the Mediterranean Sea, such as dusky grouper (100% of the examined specimens), common dentex (65%), conger (45%), common sole (38%), hake (26%) and angler (15%), among others. The estimated weekly intakes (EWI) in children (7–12 years of age) and adults from the Spanish population (2.7 µg/kg bw and 2.1 µg/kg bw, respectively) for population only consuming Mediterranean fish were below the provisional tolerable weekly intake (PTWI) of THg established by EFSA in 2012, 4 µg/kg bw. However, the equivalent estimations for methylmercury, involving PTWI of 1.3 µg/kg bw, were two times higher in children and above 50% in adults. For hake, sole, angler and dusky grouper, the most frequently consumed fish, the estimated weekly intakes in both children and adults were below the maximum levels accepted. These intakes correspond to maximum potential estimations because fish from non-Mediterranean origin is often consumed by the Spanish population including the one from the Balearic Islands.