The P-wave travel time data from the earthquakes offshore and onshore around the Black Sea are used for the tomographic reconstruction of the threedimensional (3D) velocity distribution in the lithosphere of the region. The preliminary refinement of the foci parameters (the coordinates and origin time) has reduced the random errors in the travel-time data. The earthquake data were supplemented by the previous deep seismic sounding (DSS) data on the profiles in Crimea and offshore off the Black Sea. The dataset included more than 4000 travel times overall. In order to eliminate the crustal effect, the travel times were reduced to a surface at a depth of 35 km corresponding to the mean Moho depth in the region. The improved crustal model was used for removing the contribution of the crust from the initial data. The new tomography method, which was recently developed by one of the authors and which relies on the assumption of smoothness of the lateral velocity variations, was applied for reconstructing the veloc