We report a systematic and comprehensive computational study of surface reconstructions on GaN and InN surfaces in various orientations, including the polar c plane as well as the nonpolar a and m planes. For GaN we have identified several new metallic reconstructions under highly Ga-rich conditions on the nonpolar planes. For InN we find several distinct differences from the GaN case: the absence of a nitrogen-adatom reconstruction on the (0 0 0 1) plane; the presence of a single, metallic reconstruction over the entire stability range on the plane; and In-adlayer reconstructions on the (m) plane. An interesting “inverted polarity” defect structure on the (m) plane is also revealed.