The phase velocities of Rayleigh waves provide basic information for estimating the shear-wave velocity structure of the ground. Many methods have been proposed for this purpose; however, it is difficult to estimate phase velocities directly from the data found in microtremor records on the differences in phase angles between two sites. The reason for this difficulty is that the sources of microtremors are not stable in either time or space. In order to counteract this problem, therefore, we consider the nonstationary characteristic of microtremors in short-time range and propose a method that can find the instantaneously corresponding portions of microtremor records at two different sites and that can estimate the apparent phase velocities between the two sites. We use the technique of a time-frequency analysis for which the Hilbert–Huang Transform is adopted. After we confirm the applicability of the proposed method based on some numerical calculations, the method is applied to some actual data on microtremors and reasonable results are obtained.