Correlative light and electron cryo-microscopy (cryo-CLEM) combines information from the specific labeling of fluorescence cryo-microscopy (cryo-FM) with the high resolution in environmental context of electron cryo-microscopy (cryo-EM). Exploiting super-resolution methods for cryo-FM is advantageous, as it enables the identification of rare events within the environmental background of cryo-EM at a sensitivity and resolution beyond that of conventional methods. However, due to the need for relatively high laser intensities, current super-resolution cryo-CLEM methods require cryo-protectants or support films which can severely reduce image quality in cryo-EM and are not compatible with many samples, such as mammalian cells. Here, we introduce cryogenic super-resolution optical fluctuation imaging (cryo-SOFI), a low-dose super-resolution imaging scheme based on the SOFI principle. As cryo-SOFI does not require special sample preparation, it is fully compatible with conventional cryo-EM specimens, and importantly, it does not affect the quality of cryo-EM imaging. By applying cryo-SOFI to a variety of biological application examples, we demonstrate resolutions up to ∼135 nm, an improvement of up to three times compared with conventional cryo-FM, while maintaining the specimen in a vitrified state for subsequent cryo-EM. Cryo-SOFI presents a general solution to the problem of specimen devitrification in super-resolution cryo-CLEM. It does not require a complex optical setup and can easily be implemented in any existing cryo-FM system.