The structural, electronic and magnetic properties of pristine and oxygen-adsorbed (3,0) zigzag and (6,1) armchair graphene nanoribbons have been investigated theoretically, by employing the ab initio pseudopotential method within the density functional scheme. The zigzag nanoribbon is more stable with antiferromagnetically coupled edges, and is semiconducting. The armchair nanoribbon does not show any preference for magnetic ordering and is semiconducting. The oxygen molecule in its triplet state is adsorbed most stably at the edge of the zigzag nanoribbon. The Stoner metallic behaviour of the ferromagnetic nanoribbons and the Slater insulating (ground state) behaviour of the antiferromagnetic nanoribbons remain intact upon oxygen adsorption. However, the local magnetic moment of the edge carbon atom of the ferromagnetic zigzag ribbon is drastically reduced, due to the formation of a spin-paired C-O bond. (C) 2010 Elsevier B. V. All rights reserved.