Tissues used for clinical diagnostics are mostly formalin-fixed and paraffin-embedded (FFPE) which provides many advantages. However, the quality of the obtained nucleic acids (NA) is reduced and this turns out to be a challenge for further molecular analyses. Although the spectrum of analyses of NA extracted from FFPE tissue has increased, the standard operating procedures for NA isolation from old tissue blocks still need to be improved. Here, we compared the efficiency of different NA extraction methods, using FFPE tissues of variable age and origin, with respect to downstream analyses. Our study showed that the phenol-chloroform isoamyl alcohol (PCI) and the commercial Qiagen protocol yielded samples with highest purity. The PCI protocol delivered the longest amplicons even from samples from the 1970s. We developed a short (1 h) tissue lysis procedure that turned out to be highly time- and cost-effective when DNA quality was tested using single and multiplex PCR. Compared to a 1-day lysis-protocol, the amplicons were only 100 bp shorter. In addition, single-copy genes used in daily routine were successfully amplified from long-term stored FFPE samples following 1-h tissue-lysis. The RNA integrity numbers (RIN) determined on RNA isolated from FFPE tissues indicated degraded RNA; however, all RINs were above the generally agreed threshold of 1.4. We showed that, depending on the purpose of the analysis, NA retrieved from FFPE tissues older than 40 years may be successfully used for molecular analysis.