Formalin-fixed paraffin-embedded (FFPE) tissue blocks are widely used to identify clinically actionable molecular alterations or perform retrospective molecular studies. Our goal was to quantify degradation of DNA occurring during mid to long-term storage of samples in usual conditions. We selected 46 FFPE samples of surgically resected carcinomas of lung, colon, and urothelial tract, of which DNA had been previously extracted. We performed a second DNA extraction on the same blocks under identical conditions after a median period of storage of 5.5 years. Quantitation of DNA by fluorimetry showed a 53% decrease in DNA quantity after storage. Quantitative PCR (qPCR) targeting KRAS exon 2 showed delayed amplification of DNA extracted after storage in all samples but one. The qPCR/fluorimetry quantification ratio decreased from 56 to 15% after storage (p < 0.001). Overall, remaining proportion of DNA analyzable by qPCR represented only 11% of the amount obtained at first extraction. Maximal length of amplifiable DNA fragments assessed with a multiplex PCR was reduced in DNA extracted from stored tissue, indicating that DNA fragmentation had increased in the paraffin blocks during storage. Next-generation sequencing was performed on 12 samples and showed a mean 3.3-fold decrease in library yield and a mean 4.5-fold increase in the number of single-nucleotide variants detected after storage. In conclusion, we observed significant degradation of DNA extracted from the same FFPE block after 4 to 6 years of storage. Better preservation strategies should be considered for storage of FFPE biopsy specimens.