Visual tracking techniques based on stereo endoscope are developed to measure tissue motion in robot-assisted minimally invasive surgery. However, accurate 3D tracking of tissue surfaces remains challenging due to complicated deformation, poor imaging conditions, specular reflections and other dynamic effects during surgery. This study employs a robust and efficient 3D tracking scheme with two independent recursive processes, namely kernel-based inter-frame motion estimation and model-based intra-frame 3D matching. In the first process, target region is represented in joint spatial-color space for robust estimation. By defining a probabilistic similarity measure, a mean-shift-based iterative algorithm is derived for location of the target region in a new image. In the second process, the thin-plate spline model is used to fit the 3D shape of tissue surfaces around the target region. An iterative algorithm based on an efficient second-order minimization technique is derived to compute optimal model parameters. The two processes can be computed in parallel. Their outputs are combined to recover 3D information about the target region. The performance of the proposed method is validated using phantom heart videos and in vivo videos acquired by the daVinci® surgical robotic platform and a synthesized data set with known ground truth.