The percentage of massive main-sequence OB stars in binary systems is thought to be as high as 100%. However, very few Galactic binary red supergiants (RSGs) have been identified, despite the fact that these stars are the evolved descendants of OB stars. As shown in our recent paper, binary RSGs will likely have B-type companions, as dictated by stellar evolution considerations. Such a system will have a very unique photometric signature due to the shape of the spectral energy distribution. Using photometric cutoffs, it should therefore be possible to detect candidate RSG+B star binary systems. Here we present our spectroscopic follow-up observations of such candidates. Out of our initial list of 280 candidates in M31 and M33, we observed 149 and confirmed 63 as newly discovered RSG+B star binary systems. Additional spectra of four candidate systems in the Small Magellanic Cloud confirmed all of them as new RSG+B star binaries including the first known RSG+Be star system. By fitting BSTAR06 and MARCS model atmospheres to the newly obtained spectra, we place estimates on the temperatures and subtypes of both the B stars and RSGs. Overall, we have found 87 new RSG+B star binary systems in M31, M33 and the Small and Large Magellanic Clouds. Our future studies are aimed at determining the binary fraction of RSGs.