We investigate the origin of the broad luminescence observed around 2.7-2.9 eV in heavily Mg-doped GaN through first-principles pseudopotential calculations. We And that a defect complex composed of an ME interstitial (Mg-i) and an N vacancy (V-N) gives rise to optical transition levels around 2.8 eV above the valence band maximum, suggesting that the blue luminescences are caused by deep-donor-to-valence-band transitions. The formation of the Mg-i-V-N complex is enhanced by hydrogenation and is more preferable in p-type samples grown under Cra-rich conditions.