We propose an extension of replica-exchange Monte Carlo method for canonical ensemble to isothermal-isobaric ensemble as an effective method to search for stable states quickly and widely in complex configuration space. We investigated the efficiency of the new method on a benchmark testing system which consists of 256 Lennard-Jones particles. The new method enables us to shorten dramatically the relaxation time of phase change from liquid structure to crystal structure in comparison with the conventional Monte Carlo method.