Carbon-based electronics is a promising alternative to traditional silicon-based electronics as it could enable faster, smaller and cheaper transistors, interconnects and memory devices. However, the development of carbon-based memory devices has been hampered either by the complex fabrication methods of crystalline carbon allotropes or by poor performance. Here we present an oxygenated amorphous carbon (a-COx) produced by physical vapour deposition that has several properties in common with graphite oxide. Moreover, its simple fabrication method ensures excellent reproducibility and tuning of its properties. Memory devices based on a-COx exhibit outstanding non-volatile resistive memory performance, such as switching times on the order of 10 ns and cycling endurance in excess of 104 times. A detailed investigation of the pristine, SET and RESET states indicates a switching mechanism based on the electrochemical redox reaction of carbon. These results suggest that a-COx could play a key role in non-volatile memory technology and carbon-based electronics.