Photoplethysmographic (PPG) signals are easily corrupted by motion artifacts when the subjects perform physical exercise. This paper introduces a two-step processing scheme to estimate heart rate (HR) from wrist-type PPG signals strongly corrupted by motion artifacts. Adaptive noise cancellation, using normalized least-mean-square algorithm, is first performed to attenuate motion artifacts and reconstruct multiple PPG waveforms from different combinations of corrupted PPG waveforms and accelerometer data. An adaptive band-pass filter is then used to track the common instantaneous frequency component (i.e. HR) of the reconstructed PPG waveforms. The proposed HR estimation scheme was evaluated on two datasets, composed of records from running subjects and subjects performing different kinds of arm/forearm movements and resulted in average absolute errors of 1.40  ±  0.60 and 4.28  ±  3.16 beats-per-minute for these two datasets, respectively. Importantly, the proposed method is fully automatic, induces an average estimation delay of 0.93 s, and is therefore suitable for real-time monitoring applications.