No consensus exists on the tectonic evolution of the western Mediterranean since ~35 Ma. Three disparate tectonic evolution scenarios are identified, each portraying slab rollback as the driving mechanism but with rollback starting from strongly different subduction geometries. As a critical test for the validity of each tectonic scenario we employ thermo-mechanical modeling of the 3-D subduction evolution. From each tectonic scenario we configure an initial condition for numerical modeling that mimics the perceived subduction geometry at ~35 Ma. We seek to optimize the fit between observed and predicted slab morphology by varying the nonlinear viscoplastic rheology for mantle, slab, and continental margins. From a wide range of experiments we conclude that a tectonic scenario that starts from NW-dipping subduction confined to the Balearic margin at ~35 Ma is successful in predicting present-day slab morphology. The other two scenarios (initial subduction from Gibraltar to the Baleares, and initial subduction under the African margin) lead to mantle structure much different from what is tomographically imaged. The preferred model predicts slab rotation by more than 180°, east-west lithosphere tearing along the north African margin, and a resulting steep east-dipping slab under the Gibraltar Strait. The preferred subduction model also meets the first order temporal constraints corresponding to Mid-Miocene (~16 Ma) thrusting of the Kabylides onto the African margin and nearly stalled subduction under the Rif-Gibraltar-Betic arc since the Tortonian (~8 Ma). Our modeling also provides constraints on the rheological properties of the mantle and slab, and of continental margins in the region.