In spite of clear fan-shaped magnetic anomalies in the Eastern Algerian Basin (EAB), the way how and the time when seafloor spreading occurred are still debated. In this work, a new seismo-stratigraphic interpretation based on deep-penetration reflection seismic data correlated to reduced-to-the-pole magnetic anomalies and to onshore-offshore litho-stratigraphic correlation of Pre-Messinian units bring new constraints on its age and mode of opening. Our results reveal that the seafloor spreading of EAB occurred with a intermediate to fast half-spreading rate of 3.7±0.5 cm/yr during 2.45±0.18 Myr in Langhian-Serravalian times, i.e. after the Corsica-Sardinia block rotation and the collision of Lesser Kabylia with Africa. We revise the kinematics of the Algero-Balearic domain into three stages: (1) birth of a highly stretched continental basin accommodating the southern drift of the Kabylies driven by Tethyan slab rollback between ~23 and ~15 Ma, (2) fast opening of a new basin (EAB) between 15.2 and 12.7 Ma by clockwise rotation of a Greater Alboran Block (GALB), and (3) continuation of westward translation of the GALB. The last stages match both the late formation of Subduction-Transform Edge Propagator (STEP) faults at the toes of the Algero-Balearic margins and the post-collisional volcanic migration along the Algerian margin interpreted as related to slab break-off. This new scheme invalidates most previous opening models of the Algero-Balearic basin and favors a significant stretching and splitting of the GALB into several continental fragments resulting from the westward propagation of the arcuate subduction front by lateral tearing of a narrow slab.