Sedimentary cover has significant influence on seismic wave travel times and knowing its structure is of great importance for studying deeper structures of the Earth. Seismic tomography is one of the methods that require good knowledge of seismic velocities in sediments and unfortunately by itself cannot provide detailed information about distribution of seismic velocities in sedimentary cover. This paper presents results of P-wave velocity analysis in the old Paleozoic sediments in area of Polish Lowland, Folded Area, and all sediments in complicated area of the Carpathian Mountains in Poland. Due to location on conjunction of three major tectonic units — the Precambrian East European Craton, the Paleozoic Platform of Central and Western Europe, and the Alpine orogen represented by the Carpathian Mountains the maximum depth of these sediments reaches up to 25 000 m in the Carpathian Mountains. Seismic velocities based on 492 deep boreholes with vertical seismic profiling and a total of 741 vertical seismic profiles taken from 29 seismic refraction profiles are analyzed separately for 14 geologically different units. For each unit, velocity versus depth relations are approximated by second or third order polynomials.