We report on the structural, magnetic, and superconducting properties of single and double atomic layers of Mn on a clean and unreconstructed Nb(110) substrate. Low-temperature scanning tunneling spectroscopy measurements reveal a proximity-induced superconducting state and in-gap Yu-Shiba-Rusinov bands in the Mn thin films, which are found to grow pseudomorphically on the Nb surface. Spin-polarized scanning tunneling microscopy measurements reveal a c(2×2) antiferromagnetic (AFM) order in the Mn layers, with an out-of-plane spin orientation. First-principles density functional theory calculations confirm the experimentally observed magnetic state, which is understood as the consequence of a strong intralayer and interlayer nearest-neighbor AFM exchange coupling. These results are expected to be of importance for the design of superconducting AFM spintronic systems and quantum information technologies.