Profile 1-AP with a length of 1300 km intersects the Barents Sea from The Kola Peninsula to Franz Josef Land. The combined Common Depth Point (CDP) and Deep Seismic Sounding (DSS) seismic studies were carried out on this profile. The DSS measurements were conducted with the standalone bottom seismic stations with an interval of 5–20 km between them. The stations recorded the signals generated by the large air guns with a step of 250 m. Based on these data, the detailed P-velocity section of the Earth’s crust and uppermost mantle have been constructed for the entire profile and the S-velocity section for its southern part. The use of a variety of methods for constructing the velocity sections enabled us to assess the capabilities of each method from the standpoint of the highest reliability and informativity of the models. The ray tracing method yielded the best results. The 1-PR profile crosses two large basins—the South Barents and North Barents ones, with the thickness of the sediments increasing from 8 to 10 km in the south to 12–15 km in the north. The Earth’s crust pertains to the continental type along the entire profile. Its thickness averages 32 to 36 km and only increases to 43 km at the boundary between the two basins. The distinct change in the wave field at this boundary suggests the presence of a large deep fault in this zone. The high-velocity blocks are revealed in the crust of the South Barents basin, whereas the North Barents crust is characterized by relatively low velocities.