The nanostructuring of rutile MnO2 has been demonstrated to improve its performance for electrochemical storage and catalysis. Despite the progress of recent experimental works in exploiting this to enhance the material's performance in important technological systems such as Li-ion batteries the detailed atomic-scale mechanisms still require explanation. The ability of surfaces and interfaces to produce intriguing phenomena including superconductivity and magnetism has been firmly established by intensive research in recent years. In this work we use density functional theory calculations to demonstrate that key surfaces of rutile MnO2 possess electronically conducting surface states, in contrast to the insulating bulk material. The surface band structure demonstrates that the conducting states are associated with both surface manganese and oxygen sites. Furthermore, the metallic conductivity is found to be anisotropic for the (001) surface, which may be exploited in device applications. The implications for the energy storage capacity and catalytic activity of rutile MnO2 are discussed in light of the need for good electron transport in Li-ion batteries, supercapacitors, and Li-O2 batteries.