We have developed a new simulation algorithm for free-energy calculations. The method is a multidimensional extension of the replica-exchange method. While pairs of replicas with different temperatures are exchanged during the simulation in the original replica-exchange method, pairs of replicas with different temperatures and/or different parameters of the potential energy are exchanged in the new algorithm. This greatly enhances the sampling of the conformational space and allows accurate calculations of free energy in a wide temperature range from a single simulation run, using the weighted histogram analysis method.