We propose a minimum cost path approach to track the centerlines of the internal and external carotid arteries in multispectral MR data. User interaction is limited to the annotation of three seed points. The cost image is based on both a measure of vessel medialness and lumen intensity similarity in two MRA image sequences: Black Blood MRA and Phase Contrast MRA. After intensity inhomogeneity correction and noise reduction, the two images are aligned using affine registration. The two parameters that control the contrast of the cost image were determined in an optimization experiment on 40 training datasets. Experiments on the training datasets also showed that a cost image composed of a combination of gradient-based medialness and lumen intensity similarity increases the tracking accuracy compared to using only one of the constituents. Furthermore, centerline tracking using both MRA sequences outperformed tracking using only one of these MRA images. An independent test set of 152 images from 38 patients served to validate the technique. The centerlines of 148 images were successfully extracted using the parameters optimized on the training sets. The average mean distance to the reference standard, manually annotated centerlines, was 0.98 mm, which is comparable to the in-plane resolution. This indicates that the proposed method has a high potential to replace the manual centerline annotation.