We have fabricated nanoscale fuses from CVD graphene sheets with a 'bow tie' geometry for write-once-read-many data storage applications. The fuses are programmed using thermal oxidation driven by Joule heating. Fuses that were 250 nm wide with 2.5 μm between contact pads were programmed with average voltages and powers of 4.9 V and 2.1 mW, respectively. The required voltages and powers decrease with decreasing fuse sizes. Graphene shows extreme chemical and electronic stability; fuses require temperatures of about 400 °C for oxidation, indicating that they are excellent candidates for permanent data storage. To further demonstrate this stability, fuses were subjected to applied biases in excess of typical read voltages; stable currents were observed when a voltage of 10 V was applied to the devices in the off state and 1 V in the on state for 90 h each.