A detailed sedimentological and paleontological analysis of the uppermost Miocene (Messinian)–Pliocene boundary at the northern border of the Bajo Segura Basin, southeastern Spain, was carried out in order to describe the evolution of the regional paleocoastline during the Pliocene reflooding of the Mediterranean immediately after the sea-level fall related to the Messinian Salinity Crisis. Multiple trace fossils typical of firm- and hardgrounds were recognized, allowing identification of Glossifungites (two different types), Entobia, and Gnathichnus ichnofacies. Trace-fossil analysis showed that lithology and media consistency exerted considerable control on the development of the different ichnocoenoses and that there was a clear decrease in hydrodynamic energy from a coastal to a shallow-water shelf environment related to progressive sea-level rise. Ichnological and sedimentological data provide evidence that the definitive flooding of the Mediterranean was rapid and synchronous throughout the northern margin of the Bajo Segura Basin. The following model for the Pliocene transgression in the study area is therefore proposed: (1) the marine ingression penetrated along the incised paleovalleys carved as a consequence of the fall in sea level, where the first two Pliocene systems were deposited (P0–P1); (2) during the maximum flooding surface of the transgression, the sea overflowed the margins of the paleovalleys and extended throughout the entire northern margin of the basin; and (3) the third Pliocene system was deposited, forming the lower part of a highstand systems tract (P2).