A number of different geodynamic models have been proposed to explain the extension that occurred during the Miocene in the Alboran Sea region of the western Mediterranean despite the continued convergence and shortening of northern Africa and southern Iberia. In an effort to provide additional geophysical constraints on these models, we performed a local, regional, and teleseismic tomographic travel time inversion for the lithospheric and upper mantle velocity structure and earthquake locations beneath the Alboran region in an area of 800¿800 km2. We picked P and S arrival times from digital and analog seismograms recorded by 96 seismic stations in Morocco and Spain between 1989 and 1996 and combined them with arrivals carefully selected from local and global catalogs (1964--1998) to generate a starting data set containing over 100,000 arrival times. Our results indicate that a N-S line of intermediate-depth earthquakes extending from crustal depths significantly inland from the southern Iberian coast to depths of over 100 km beneath the center of the Alboran Sea coincides with a W to E transition from high to low velocities imaged in the uppermost mantle. A high-velocity body, striking approximately NE-SW, is imaged to dip southeastwards from lithospheric depths beneath the low-velocity region to depths of ~350 km. Between 350 and 500 km the imaged velocity anomalies become more diffuse. However, pronounced high-velocity anomalies are again imaged at 600 km near an isolated cluster of deep earthquakes. In addition to standard tomographic methods of error assessment, the effects of systematic and random errors were assessed using block shifting and bootstrap resampling techniques, respectively. We interpret the upper mantle high-velocity anomalies as regions of colder mantle that originate from lithospheric depths. These observations, when combined with results from other studies, suggest that delamination of a continental lithosphere played an important role in the Neogene and Quaternary evolution of the region. ¿ 2000 American Geophysical Union