We propose a novel trellis-based peak frequency tracking technique for photoplethysmographic (PPG) heart rate (HR) sensing. Dealing with HR changes on the time-frequency plane obtained by the Short Time-Discrete Fourier Transform as state transitions in a trellis diagram, the proposed technique rejects outliers induced during exercise. Experimental result involving thirteen subjects reveals that the proposed peak frequency tracking technique, which is combined with the recursive least squares algorithm-based MA cancellation technique, can achieve the root mean squares percent error of 6.924 % for a series of exercises with various intensities.