Robotic assisted beating heart surgery aims to allow surgeons to operate on a beating heart without stabilizers as if the heart is stationary. The robot actively cancels heart motion by closely following a point of interest (POI) on the heart surface—a process called Active Relative Motion Canceling (ARMC). Due to the high bandwidth of the POI motion, it is necessary to supply the controller with an estimate of the immediate future of the POI motion over a prediction horizon in order to achieve sufficient tracking accuracy. In this paper, two least-square based prediction algorithms, using an adaptive filter to generate future position estimates, are implemented and studied. The first method assumes a linear system relation between the consecutive samples in the prediction horizon. On the contrary, the second method performs this parametrization independently for each point over the whole the horizon. The effects of predictor parameters and variations in heart rate on tracking performance are studied with constant and varying heart rate data. The predictors are evaluated using a 3 degrees of freedom test-bed and prerecorded in-vivo motion data. Then, the one-step prediction and tracking performances of the presented approaches are compared with an Extended Kalman Filter predictor. Finally, the essential features of the proposed prediction algorithms are summarized.