© 2013 IEEE. Analyzing cerebrovascular changes can significantly lead to not only detecting the presence of serious diseases e.g., hypertension and dementia, but also tracking their progress. Such analysis could be better performed using Time-of-Flight Magnetic Resonance Angiography (ToF-MRA) images, but this requires accurate segmentation of the cerebral vasculature from the surroundings. To achieve this goal, we propose a fully automated cerebral vasculature segmentation approach based on extracting both prior and current appearance features that have the ability to capture the appearance of macro and micro-vessels in ToF-MRA. The appearance prior is modeled with a novel translation and rotation invariant Markov-Gibbs Random Field (MGRF) of voxel intensities with pairwise interaction analytically identified from a set of training data sets. The appearance of the cerebral vasculature is also represented with a marginal probability distribution of voxel intensities by using a Linear Combination of Discrete Gaussians (LCDG) that its parameters are estimated by using a modified Expectation-Maximization (EM) algorithm. The extracted appearance features are separable and can be classified by any classifier, as demonstrated by our segmentation results. To validate the accuracy of our algorithm, we tested the proposed approach on in-vivo data using 270 data sets, which were qualitatively validated by a neuroradiology expert. The results were quantitatively validated using the three commonly used metrics for segmentation evaluation: the Dice coefficient, the modified Hausdorff distance, and the absolute volume difference. The proposed approach showed a higher accuracy compared to two of the existing segmentation approaches.