Remote heart rate (HR) estimation from videos is useful because it facilitates monitoring ongoing health conditions without sensors that are often uncomfortable to wear. In the HR estimation from videos, choice of the image region, at which the HR is calculated, is critically important as it greatly affects the estimation accuracy. In this paper, a novel algorithm for HR estimation that uses dynamic region selection is proposed. The image regions that clearly contain pulse waveforms are quickly found by a region selector using a machine learning technique. In addition, the proposed method enhances the robustness of tracking the temporal change of the HR by using a particle filter. The experimental results show that the proposed method achieves the absolute average error less than 1.1BPM (Beats Per Minute) with the processing time less than 0.6s for a single HR estimation.