We introduce a new optimization algorithm that combines the basin-hopping method, which can be used to efficiently map out an energy landscape associated with minima, with the multicanonical Monte Carlo method, which encourages the system to move out of energy traps during the computation. As an example of implementing the algorithm for the global minimization of a multivariable system, we consider the Lennard-Jones systems containing 150-185 particles, and find that the new algorithm is more efficient than the original basin-hopping method. (C) 2004 American Institute of Physics.