The effect of trace arsenic on the growth and surface structure of GaN(0 0 0 1) has been studied. We find that a partial pressure of only 10−9 Torr of arsenic during molecular beam epitaxial growth significantly modifies the growth kinetics. Such a small background pressure of arsenic leads to an arsenic-terminated surface displaying a 2×2 reconstruction during growth which is absent for the clean surface. First-principles theoretical calculations show that As-terminated surfaces are energetically more favorable than Ga-terminated surfaces for arsenic pressures of 10−9 Torr, and structural models for the As-adatom 2×2 reconstruction are presented.