We study the energetics of Mg-related defects in GaN through first-principles pseudopotential calculations. In p-type GaN, Mg-Ga(-) accepters are found to be compensated by V-N(+) donors and also deactivated by the formation of complexes such as Mg-Ga-V-N and Mg-i-V-N. We suggest that a Mg-i-V-N complex, which consists of a Mg interstitial and a N-vacancy, is responsible for the blue luminescence observed in heavily Mg-doped GaN. Although this defect complex is easily passivated by three hydrogen atoms, thermal annealing recovers the activity of this complex and thereby increases the intensity of the blue luminescence.