Most interpretations of the Early Pliocene opening of the Strait of Gibraltar involve a tectonic process. However, no tectonic structure of this age has been unequivocally documented that could account for such a hypothesis. On the other hand, the sea-level drop of the Mediterranean during the Messinian Salinity Crisis has dramatically enhanced continental erosion and in particular regressive fluvial erosion. We show that such erosional process inevitably developed in the Gibraltar area. We finally propose that regressive fluvial erosion was at the origin of the opening of the Strait of Gibraltar.