To achieve whole-brain segmentation—i.e., classifying tissues within and immediately around the brain as gray matter (GM), white matter (WM), and cerebrospinal fluid—magnetic resonance (MR) imaging is nearly always used. However, there are many clinical scenarios where computed tomography (CT) is the only modality that is acquired and yet whole brain segmentation (and labeling) is desired. This is a very challenging task, primarily because CT has poor soft tissue contrast; very few segmentation methods have been reported to date and there are no reports on automatic labeling. This paper presents a whole brain segmentation and labeling method for non-contrast CT images that first uses a fully convolutional network (FCN) to synthesize an MR image from a CT image and then uses the synthetic MR image in a standard pipeline for whole brain segmentation and labeling. The FCN was trained on image patches derived from ten co-registered MR and CT images and the segmentation and labeling method was tested on sixteen CT scans in which co-registered MR images are available for performance evaluation. Results show excellent MR image synthesis from CT images and improved soft tissue segmentation and labeling over a multi-atlas segmentation approach.