The stability of graphene nanoribbons in the presence of typical atmospheric molecules is systematically investigated by means of density-functional theory. We calculate the edge formation free energy of five different edge configurations passivated by H, H-2, O, O-2, N-2, CO, CO2, and H2O, respectively. In addition to the well known hydrogen passivated armchair and zigzag edges, we find the edges saturated by oxygen atoms to be particularly stable under atmospheric conditions. Saturation of the zigzag edge by oxygen leads to the formation of metallic states strictly localized on the oxygen atoms. Finally, the vibrational spectrum of the hydrogen- and oxygen-passivated ribbons are calculated and compared.