We investigate the properties of Mg acceptors in nitride semiconductors with hybrid functional calculations. We find that although the thermodynamic transition level is relatively close to the valence band in GaN (260 meV), Mg(Ga) exhibits key features of a deep acceptor: the hole is localized on a N atom neighboring the Mg impurity, inducing a large local lattice distortion and giving rise to broad blue luminescence. We show that the ultraviolet photoluminescence peak attributed to Mg acceptors in GaN is likely related to Mg-H complexes, explaining the results of photoluminescence and electron paramagnetic resonance experiments. Predictions for Mg acceptors in AlN and InN are also presented.