Non-linear inverse problems arising in seismology are usually addressed either by linearization or by Monte Carlo methods. Neither approach is flawless. The former needs an accurate starting model; the latter is computationally intensive. Both require careful tuning of inversion parameters. An additional challenge is posed by joint inversion of data of different sensitivities and noise levels such as receiver functions and surface wave dispersion curves. We propose a generic workflow that combines advantages of both methods by endowing the linearized approach with an ensemble of homogeneous starting models. It successfully addresses several fundamental issues inherent in a wide range of inverse problems, such as trapping by local minima, exploitation of a priori knowledge, choice of a model depth, proper weighting of data sets characterized by different uncertainties, and credibility of final models. Some of them are tackled with the aid of novel 1D checkerboard tests—an intuitive and feasible addition to the resolution matrix. We applied our workflow to study the south-western margin of the East European Craton. Rayleigh wave phase velocity dispersion and P-wave receiver function data were gathered in the passive seismic experiment “13 BB Star” (2013–2016) in the area of the crust recognized by previous borehole and refraction surveys. Final models of S-wave velocity down to 300 km depth beneath the array are characterized by proximity in the parameter space and very good data fit. The maximum value in the mantle is higher by 0.1–0.2 km/s than reported for other cratons.