In this paper, we present results of 3-D first-arrival tomography applied to data recorded in SE Poland during the CELEBRATION 2000 seismic experiment. The target area covers ca. 500 × 500 km2 and represents a complex geological setting from old Precambrian platform (East European Craton, EEC), through the crustal blocks (terranes) that form the Trans-European Suture Zone (TESZ) to the young Alpine orogen—the Carpathians. Contrasting velocity distributions in various geological units makes the tomographic inversion challenging. For this reason, much attention was paid to the inversion methodology. We tested ‘multioffset’ and ‘multiscale’ approaches. By increasing the offset range in the ‘multioffset’ inversion we have independently constrained different depth ranges of our model. We have found that the ‘multiscale’ method, that is, the gradual stepping from bigger to smaller model cells produced the preferred solution. Resolution of the resultant crustal model was determined by performing checkerboard and restoration resolution tests. Lateral resolution of the order of 25 km is inferred down to 10 km depth and 50 km down to 25–30 km depth. We have also applied a quasi-Monte Carlo analysis to determine the absolute errors of model parameters, which to our knowledge, is the first such attempt in case of a 3-D wide-angle data set. The mean uncertainties of our tomographic velocities are 0.1 km s−1, but some anomalies are recovered with larger errors. We also advocate that the results from the central part of the Małopolska Block (MB) are biased by the influence of crustal anisotropy as confirmed by an independent study. The overall picture of the transition from the EEC to the TESZ resembles an Atlantic-type passive margin, with several high velocity bodies occurring along the EEC edge and relatively low velocities (VP < 6 km s−1) extending down to ca. 20 km. Of the crustal units investigated, the Upper Silesian Block (USB) fully deserves to be called a terrane. It is distinct in terms of seismic velocities and its eastern edge (Kraków–Lubliniec Fault) is clearly visible and continues beneath the Carpathian nappes. The differences between the overall crustal structure of the MB and the Łysogóry Unit (LU) are minor and thus the ‘terrane’ concept does not necessarily apply to them.