Description: The continuation of the Caledonides into the Barents Sea has long been a subject of discussion, and two major orientations of the Caledonian deformation fronts have been suggested: NNW-SSE striking and NE-SW striking. A regional NW-SE oriented ocean bottom seismic profile across the western Barents Sea was acquired in 2014. In this paper we map the crust and upper mantle structure along this profile in order to discriminate between different interpretations of Caledonian structural trends and orientation of rift basins in the western Barents Sea. Modeling of P-wave travel times has been done using a ray-tracing method, and combined with gravity modeling. The results show high P-wave velocities (4 km/s) close to the seafloor, as well as localized sub-horizontal high velocity zones (6.0 km/s and 6.9 km/s) at shallow depths which are interpreted as magmatic sills. Refractions from the top of the crystalline basement together with reflections from the Moho give basement velocities from 6.0 km/s at the top to 6.7 km/s at the base of the crust. P-wave travel time modeling of the OBS profile indicate an eastwards increase in velocities from 6.4 km/s to 6.7 km/s at the base of the crystalline crust, and the western part of the profile is characterized by a higher seismic reflectivity than the eastern part. This change in seismic character is consistent with observations from vintage reflection seismic data and is interpreted as a Caledonian suture extending through the Barents Sea, separating Barentsia and Baltica. Local deepening of Moho (from 27 km to 33 km depth) creates “root structures” that can be linked to the Caledonian compressional deformation or a suture zone imprinted in the lower crust. Our model supports a separate NE-SW Caledonian trend extending into the central Barents Sea, branching off from the northerly trending Svalbard Caledonides, implying the existence of Barentsia as an independent microcontinent between Laurentia and Baltica.