The co-doping of graphene with nitrogen and sulfur was investigated aiming at understanding their interactions with the presence of oxygen in graphene. The co-doped graphene (NS-G) was synthesized via a one-pot hydrothermal route using graphene oxide as starting material and L-cysteine, an amino acid containing both N and S, as the doping agent. The obtained NS-G with a three-dimensional hierarchical structure containing both macropores and mesopores exhibited excellent mechanical stabilities under both wet and dry conditions. As compared to N or S singly doped graphene, the co-doped sample contains significantly higher concentrations of N and S species especially pyrollic N groups. The co-doped sample considerably outperformed the singly doped samples when used as free-standing electrode in supercapacitors due to enhanced pseudocapacitance. The simultaneous incorporation of S and N species with the presence of oxygen significantly modified the surface chemistry of carbon leading to considerably higher doping levels, although directly bonding between N and S is neither likely nor detected. Hence, the synergetic effect between N and S occurred through carbon atoms in neighboring hexagonal rings in a graphene sheet.