This paper presents a Bayesian framework for tracking of tubular structures such as vessels. Compared to conventional tracking schemes, its main advantage is its non-deterministic character, which strongly increases the robustness of the method. A key element of our approach is a dedicated observation model for tubular structures in regions with varying intensities. Furthermore, we show how the tracking method can be used to obtain a probabilistic segmentation of the tracked tubular structure. The method has been applied to track the internal carotid artery from CT angiography data of 14 patients (28 carotids) through the skull base. This is a challenging problem, owing to the close proximity of bone, overlap in intensity values of lumen voxels and (partial volume) bone voxels, and the tortuous path of the vessels. The tracking was successful in 25 cases, and the extracted path were found to be close (< 1.0mm) to manually traced paths by two observers.