Graphene-related materials are in the forefront of nanomaterial research. One of the most common ways to prepare graphenes is to oxidize graphite (natural or synthetic) to graphite oxide and exfoliate it to graphene oxide with consequent chemical reduction to chemically reduced graphene. Here, we show that both natural and synthetic graphite contain a large amount of metallic impurities that persist in the samples of graphite oxide after the oxidative treatment, and chemically reduced graphene after the chemical reduction. We demonstrate that, despite a substantial elimination during the oxidative treatment of graphite samples, a significant amount of impurities associated to the chemically reduced graphene materials still remain and alter their electrochemical properties dramatically. We propose a method for the purification of graphenes based on thermal treatment at 1,000 °C in chlorine atmosphere to reduce the effect of such impurities on the electrochemical properties. Our findings have important implications on the whole field of graphene research.