We present 23 candidate X-ray binaries with luminosities down to 1.8x10^36^erg/s, in the nearby starburst galaxy NGC 4449, from observations totaling 105ks taken with the ACIS-S instrument on the Chandra Space Telescope. We determine count rates, luminosities, and colors for each source, and perform spectral fits for sources with sufficient counts. We also compile a new catalog of 129 compact star clusters in NGC 4449 from high-resolution, multi-band optical images taken with the Hubble Space Telescope, doubling the number of clusters known in this galaxy. The UBVI, H{alpha} luminosities of each cluster are compared with predictions from stellar evolution models to estimate their ages and masses. We find strong evidence for a population of very young massive, black hole binaries, which comprise nearly 50% of the detected X-ray binaries in NGC 4449. Approximately a third of these remain within their parent star clusters, which formed {tau}<=6-8Myr ago, while others have likely been ejected from their parent clusters. We also find evidence for a population of somewhat older X-ray binaries, including both supergiant and Be-binaries, which appear to be associated with somewhat older {tau}~100-400Myr star clusters, and one X-ray binary in an ancient ({tau}~10Gyr) globular cluster. Our results suggest that detailed information on star clusters can significantly improve constraints on X-ray binary populations in star-forming galaxies.