Rupture velocity is an important source parameter, which is often difficult to determine, especially for deep-focus earthquakes where there is usually limited near-source information. To help overcome this problem, we developed a new method to estimate rupture velocities of deep-focus earthquakes with better resolution. We first carry out teleseismic P waveform inversions to determine slip distributions for a range of rupture velocities on the two nodal planes. Then forward modeling of regional data is performed using the slip distributions determined in the teleseismic inversions to estimate the rupture velocity. Using this method, we attempted to determine the rupture velocities of large deep-focus earthquakes surrounding Japan, which are well recorded on teleseismic and regional networks. Empirical Green functions are used for both the teleseismic and regional analyses. Although it is difficult to determine the rupture velocity from only the teleseismic data, the analyses including regional data show clear difference which can resolve the rupture velocity and fault geometry. For three deep earthquakes, we obtained rupture velocities of about 1∼2 km/s, which correspond to 20∼40% of the shear wave velocity and are much slower than typical values for shallow earthquakes.