© 2018. The American Astronomical Society. All rights reserved. We present a new technique to determine distances to major star-forming regions across the Perseus Molecular Cloud, using a combination of stellar photometry, astrometric data, and 12CO spectral-line maps. Incorporating the Gaia DR2 parallax measurements when available, we start by inferring the distance and reddening to stars from their Pan-STARRS1 and Two Micron All Sky Survey photometry, based on a technique presented by Green et al. and implemented in their 3D "Bayestar" dust map of three-quarters of the sky. We then refine their technique by using the velocity slices of a CO spectral cube as dust templates and modeling the cumulative distribution of dust along the line of sight toward these stars as a linear combination of the emission in the slices. Using a nested sampling algorithm, we fit these per-star distance-reddening measurements to find the distances to the CO velocity slices toward each star-forming region. This results in distance estimates explicitly tied to the velocity structure of the molecular gas. We determine distances to the B5, IC 348, B1, NGC 1333, L1448, and L1451 star-forming regions and find that individual clouds are located between ≈275 and 300 pc, with typical combined uncertainties of ≈5%. We find that the velocity gradient across Perseus corresponds to a distance gradient of about 25 pc, with the eastern portion of the cloud farther away than the western portion. We determine an average distance to the complex of 294 ± 17 pc, about 60 pc further than the distance derived to the western portion of the cloud using parallax measurements of water masers associated with young stellar objects. The method we present is not limited to the Perseus Complex, but may be applied anywhere on the sky with adequate CO data in the pursuit of more accurate 3D maps of molecular clouds in the solar neighborhood and beyond.