A new algorithm in the Gibbs ensemble is presented where statistical sampling is improved by combining the cavity-bias and parallel tempering formalisms. The parallel tempering allows the method to surmount large free energy barriers in the potential energy surface while the cavity-bias technique improves the probability of particle transfer. The method was used to construct Cailletet-Mathias curves for the liquid-vapor equilibrium of a three-dimensional Lennard-Jones fluid. An accurate computation of the critical parameters for this system was obtained. Details about the implementation of the method and a comparison with previous studies are presented. (C) 2002 Elsevier Science B.V. All rights reserved.