The properties of defect complexes consisting of a nitrogen vacancy with a substitutional beryllium or magnesium atom on neighboring lattice sites in hexagonal GaN are calculated using the AIMPRO local-density-functional theory method. Both types of defects VN−BeGa and VN−MgGa are bound with respect to their isolated constituents. They do not appear to have any electronic levels in the bandgap, and are expected to be neutral defects. Important structural differences are found. In its minimum energy configuration, the Be atom in the VN−BeGa complex lies nearly in the same plane as the three equivalent N atoms nearest to it. Thus, it has shorter Be−N bonds than the Ga−N distance in the bulk crystal, while the Mg atom in the VN−MgGa complex occupies a position closer the lattice site of the Ga atom it replaces. Hence, the VN−BeGa complex has a larger open volume than the VN−MgGa complex. This is consistent with positron annihilation experiments [Saarinen et al., J. Cryst. Growth 246, 281 (2002); Hautakangas et al., Phys. Rev. Lett. 90, 137402 (2003)]. The frequency of the highest local vibrational mode of the VN−BeGa center is calculated to be within 3–4 % of an infrared absorption line detected in Be-doped GaN [Clerjaud (private communication)].