Formalin fixed and paraffin-embedded human tissue resected during cancer surgery is indispensable for diagnostic and therapeutic purposes and represents a vast and largely unexploited resource for research. Optical microscopy of such specimen is curtailed by the diffraction-limited resolution of conventional optical microscopy. To overcome this limitation, we used STED super-resolution microscopy enabling optical resolution well below the diffraction barrier. We visualized nanoscale protein distributions in sections of well-annotated paraffin-embedded human rectal cancer tissue stored in a clinical repository. Using antisera against several mitochondrial proteins, STED microscopy revealed distinct sub-mitochondrial protein distributions, suggesting a high level of structural preservation. Analysis of human tissues stored for up to 17 years demonstrated that these samples were still amenable for super-resolution microscopy. STED microscopy of sections of HER2 positive rectal adenocarcinoma revealed details in the surface and intracellular HER2 distribution that were blurred in the corresponding conventional images, demonstrating the potential of super-resolution microscopy to explore the thus far largely untapped nanoscale regime in tissues stored in biorepositories.