We report nanoscale patterning of graphene using a helium ion microscope configured for lithography. Helium ion lithography is a direct-write lithography process, comparable to conventional focused ion beam patterning, with no resist or other material contacting the sample surface. In the present application, graphene samples on Si/SiO2 substrates are cut using helium ions, with computer controlled alignment, patterning, and exposure. Once suitable beam doses are determined, sharp edge profiles and clean etching are obtained, with little evident damage or doping to the sample. This technique provides fast lithography compatible with graphene, with approximately 15 nm feature sizes.