In the quest for room temperature spintronic materials, there have been considerable effort to attain the deposition of ferromagnetic nanostructures onto semiconductor surfaces to achieve spin polarized transport. With this drive, Mn atoms are deposited onto gallium nitride (GaN) substrates and, depending on the deposition temperature, two surface reconstructions are obtained. At low temperature, a metastable 3×3 structure forms, which upon mild annealing converts to a more stable √3×√3 structure through an irreversible phase transition. Using ab initio techniques, we propose models in consonance with the experimental findings. We find that the 3×3 structure consists of trimers of Mn adatoms, while the √3×√3 one, involves Mn atoms substituting surface Ga ions. This transition is concomitant with a change in the magnetic interactions among the Mn atoms, thus driving a magnetic transit ion along with the structural one.