This paper investigates convex belief propa-gation algorithms for Markov random fields (MRFs) with continuous variables. Our first contribution is a theorem generalizing prop-erties of the discrete case to the continuous case. Our second contribution is an algo-rithm for computing the value of the La-grangian relaxation of the MRF in the contin-uous case based on associating the continuous variables with an ever-finer interval grid. A third contribution is a particle method which uses convex max-product in re-sampling par-ticles. This last algorithm is shown to be par-ticularly effective for protein folding where it outperforms particle methods based on stan-dard max-product resampling.