We identify red supergiants (RSGs) in our spiral neighbors M31 and M33 using near-IR (NIR) photometry complete to a luminosity limit of log L/Lo=4.0. Our archival survey data cover 5 deg^2 of M31, and 3 deg^2 for M33, and are likely spatially complete for these massive stars. Gaia is used to remove foreground stars, after which the RSGs can be separated from asymptotic giant branch (AGB) stars in the color-magnitude diagram. The photometry is used to derive effective temperatures and bolometric luminosities via MARCS stellar atmosphere models. The resulting H-R diagrams show superb agreement with the evolutionary tracks of the Geneva evolutionary group. Our census includes 6400 RSGs in M31 and 2850 RSGs in M33 within their Holmberg radii; by contrast, only a few hundred RSGs are known so far in the Milky Way. Our catalog serves as the basis for a study of the RSG binary frequency being published separately, as well as future studies relating to the evolution of massive stars. Here we use the matches between the NIR-selected RSGs and their optical counterparts to show that the apparent similarity in the reddening of OB stars in M31 and M33 is the result of Malmquist bias; the average extinction in M31 is likely higher than that of M33. As expected, the distribution of RSGs follows that of the spiral arms, while the much older AGB population is more uniformly spread across each galaxys disk.