The segmentation of brain tissue into cerebrospinal fluid, gray matter, and white matter in magnetic resonance imaging scans is an important procedure to extract regions of interest for quantitative analysis and disease assessment. Manual segmentation requires skilled experts, being a laborious and time-consuming task; therefore, reliable and robust automatic segmentation methods are necessary. We propose a segmentation framework based on a Conditional Random Field for brain tissue segmentation, with a Random Forest encoding the likelihood function. The features include intensities, gradients, probability maps, and locations. Additionally, skull stripping is critical for achieving an accurate segmentation; thus, after extracting the brain we propose to refine its boundary during segmentation. The proposed framework was evaluated on the MR Brain Image Segmentation Challenge and the Internet Brain Segmentation Repository databases. The segmentations of brain tissues obtained with the proposed algorithm were competitive both in normal and diseased subjects. The skull stripping refinement significantly improved the results, when comparing against no refinement. In the MR Brain Image Segmentation Challenge database, the results were competitive when comparing with top methods. In the Internet Brain Segmentation Repository database, the proposed approach outperformed other well-established algorithms. The combination of a Random Forest and Conditional Random Field for brain tissue segmentation performed well for normal and diseased subjects. Additionally, refinement of the skull stripping at segmentation time is feasible in learning-based methods and significantly improves the segmentation of cerebrospinal fluid and intracranial volume.