Reconstructing early human colonization of the Balearic Islands in the western Mediterranean is challenging due to limited archaeological evidence. Current understanding places human arrival ~4400 years ago. Here, U-series data from phreatic overgrowth on speleothems are combined with the discovery of a submerged bridge in Genovesa Cave that exhibits a distinctive coloration band near its top. The band is at the same depth as the phreatic overgrowth on speleothems (−1.1 meters), both of which indicate a sea-level stillstand between ~6000 and ~5400 years ago. Integrating the bridge depth with a high-resolution Holocene sea-level curve for Mallorca and the dated phreatic overgrowth on speleothems level constrains the construction of the bridge between ~6000 and ~5600 years ago. Subsequent sea-level rise flooded the archeological structure, ruling out later construction dates. This provides evidence for early human presence on the island dating at least 5600 and possibly beyond ~6000 years ago. Early human groups were present in Mallorca, Spain, at least 5600 years ago, based on evidence from a submerged bridge’s coloration mark and speleothem-based relative sea level analysis.