In this paper, we introduce a stable-phase approach for hierarchical annealing which addresses the very large computational costs associated with simulated annealing for the reconstruction of large-scale binary porous media images. Our presented method, which uses the two-point correlation function as the morphological descriptor, involves the reconstruction of three-phase and two-phase structures. We consider reconstructing the three-phase structures based on standard annealing and the two-phase structures based on standard and hierarchical annealings. From the result of the two-dimensional (2D) reconstruction, we find that the 2D generation does not fully capture the morphological information of the original image, even though the two-point correlation function of the reconstruction is in excellent agreement with that of the reference image. For the reconstructed three-dimensional (3D) microstructure, we calculate its permeability and compare it to that of the reference 3D microstructure. The result indicates that the reconstructed structure has a lower degree of connectedness than that of the actual sandstone. We also compare the computation time of our presented method to that of the standard annealing, which shows that our presented method of orders of magnitude improves the convergence rate. That is because only a small part of the pixels in the overall hierarchy need to be considered for sampling by the annealer.