Despite a wide range of feature detectors developed in the computer vision community over the years, direct application of these techniques to surgical navigation has shown significant difficulties due to the paucity of reliable salient features coupled with free--form tissue deformation and changing visual appearance of surgical scenes. The aim of this paper is to propose a novel probabilistic framework to track affine-invariant anisotropic regions under contrastingly different visual appearances during Minimally Invasive Surgery (MIS). The theoretical background of the affine-invariant anisotropic feature detector is presented and a real-time implementation exploiting the computational power of the GPU is proposed. An Extended Kalman Filter (EKF) parameterization scheme is used to adaptively adjust the optimal templates of the detected regions, enabling accurate identification and matching of the tracked features. For effective tracking verification, spatial context and region similarity have also been incorporated. They are used to boost the prediction of the EKF and recover potential tracking failure due to drift or false positives. The proposed framework is compared to the existing methods and their respective performance is evaluated with in vivo video sequences recorded from robotic-assisted MIS procedures, as well as real-world scenes.