The fabrication of nano features in different functional materials - such as gold, graphene, carbon nano-tubes, and quantum dots - can open up the possibility of using them more comprehensively in micro/nano electromechanical systems (MEMS/NEMS) applications. This paper presents a feasibility investigation of fabricating nano-holes in graphene with a focus on machining at an atomic scale. The nano-metric material removal mechanism and the formation of a heat-affected zone (HAZ) due to the electro-machining (EM) process are discussed. It is demonstrated that nano-EM in a liquid dielectric medium (n-decane) is capable of fabricating features as small as 3 to 4 nm with a visible atomic arrangement of carbon in graphene. Nano-features of 5 to 6 nm can be machined consistently with excellent repeatability using the nano-EM process. As an electro-thermal machining process, nano-EM generates HAZ and results in the deposition of materials at the edge of the machined nano-holes. The dimensions of both the nano-features and HAZ increase with the increase of bias voltage and pulse duration. Gradual reconstruction of carbon lattices at the edge of the nano-holes, and thus a change in the profile of the nano-holes, are subsequently observed. Finally, it is established that batch mode nano-holes can be machined on a graphene surface using the nano-EM process, thus making the process suitable for scale-up applications.