Upscaling log measurements acquired at high frequencies and correlating them with corresponding low-frequency values from surface seismic and vertical seismic profile data is a challenging task. We have applied a sampling technique called the reversible jump Markov chain Monte Carlo (RJMCMC) method to this problem. A key property of our approach is that it treats the number of unknowns itself as a parameter to be determined. Specifically, we have considered upscaling as an inverse problem in which we considered the number of coarse layers, layer boundary depths, and material properties as the unknowns. The method applies Bayesian inversion, with RJMCMC sampling and uses simulated annealing to guide the optimization. At each iteration, the algorithm will randomly move a boundary in the current model, add a new boundary, or delete an existing boundary. In each case, a random perturbation is applied to Backus-average values. We have developed examples showing that the mismatch between seismograms computed from the upscaled model and log velocities improves by 89% compared to the case in which the algorithm is allowed to move boundaries only. The layer boundary distributions after running the RJMCMC algorithm can represent sharp and gradual changes in lithology. The maximum deviation of upscaled velocities from Backus-average values is less than 10% with most of the values close to zero.