Markov Chain Monte Carlo (MCMC) sampling of solutions to large-scale inverse problems is, by many, regarded as being unfeasible due to the large number of model parameters. This statement, however, is only true if arbitrary, local proposal distributions are used. If we instead use a global proposal, informed by the physics of the problem, we can dramatically improve the performance of MCMC and even solve highly nonlinear inverse problems with vast model spaces. This is illustrated by a seismic full-waveform inverse problem in the acoustic approximation, involving close to 10^6 parameters.