The exact exchange of density functional theory is used to calculate the electronic structure of the antiferromagnetic (type II) phases of the transition-metal monoxides MnO, FeO, CoO, and NiO at T=0. In contrast with the local density approximation (LDA) and generalized gradient approximation, the exact exchange (combined with LDA correlation) correctly yields insulating ground states for all four compounds. The values for the band gaps and magnetic moments obtained with this parameter-free first principles method are in good agreement with the experimental data. While correlation plays a major role for the electronic structure, these results demonstrate that the mere opening of a gap in FeO and CoO is already obtained on the level of density functional theory, if the exact, multiplicative exchange potential is combined with a full potential method. State-dependent potentials are not required for obtaining a gap.