The beating heart tracking based on stereo endoscope remains challenging due to highly dynamic scenes and poor imaging conditions in minimally invasive surgery. This paper proposes a new prediction method for robust tracking of heart motion. The dual time-varying Fourier series is used for modeling the motion of points of interest (POI) on heart surfaces, which is driven jointly by breathing and heartbeat motion. A dual Kalman filtering scheme is used to estimate the frequencies and Fourier coefficients of the model respectively. A novel orthogonal decomposition algorithm is developed to measure the instantaneous frequencies of breathing and heartbeat motion online from the 3D trajectory of the POI. The difference in direction between breathing and heartbeat motion is exploited by using principal component analysis on the past trajectory, and optimal 1D principal component signals are extracted for measuring the corresponding frequencies. The frequencies calculated from the orthogonal subbands are fused based on an additive noise model for optimal frequency measurement. The proposed method is evaluated and compared with other available prediction methods based on the simulated data and the real-measured signals from the videos recorded by the daVinci® surgical robot. The prediction algorithm is finally incorporated into a well-established visual tracking method to handle long-term occlusions.