We introduce a super-resolution technique for fluorescence cryo-microscopy based on photoswitching of standard genetically encoded fluorescent marker proteins in intact mammalian cells at low temperature (81 K). Given the limit imposed by the lack of cryo-immersion objectives, current applications of fluorescence cryo-microscopy to biological specimens achieve resolutions between 400-500 nm only. We demonstrate that the single molecule characteristics of reversible photobleaching of mEGFP and mVenus at liquid nitrogen temperature are suitable for the basic concept of single molecule localization microscopy. This enabled us to perform super-resolution imaging of vitrified biological samples and to visualize structures in unperturbed fast frozen cells for the first time with a structural resolution of ∼125 nm (average single molecule localization accuracy ∼40 nm), corresponding to a 3-5 fold resolution improvement.