For stereo matching, PatchMatch belief propagation (PMBP) gives an efficient way of inferencing continuous labels on the Markov random field. Nevertheless, it still requires considerable time when the resolution of input images is high. To handle high-resolution images, a two-step stereo method is proposed that efficiently exploits PMBP by depth upsampling. In the first step, PMBP is conducted on the random field whose nodes correspond to the downsampled pixels from an input image. As a result, accurate low-resolution disparity maps are efficiently obtained by taking advantage of PMBP. In the second step, the low-resolution disparity map is upsampled while considering depth boundaries and sub-pixel accuracy. Experimental results show that the proposed method provides more accurate disparity maps than the original PMBP while reducing computation time remarkably.