Adsorptions of gas molecules were found to alter the directions and magnitudes of magnetic moments of transition metal (Co, Fe) atoms adsorbed on graphene. Using first-principles calculations, we demonstrated that magnetism of surface atoms can be used to identify the kind of existing gas molecules via spin-reorientation and/or demagnetizations caused by the reconfigurations of 3d electron energy levels of Co and Fe. We suggest for the first time that magnetic properties of transition metal-embedded nanostructures can be used in highly selective gas-sensing applications.