Lung cancer is the most common cause of cancer-related deaths worldwide, and metastatic spread of the cancer rather than the primary tumor is the main cause of death. However, the molecular alterations of cancer cells leading to the formation of metastasis are poorly understood. This is partly a result of most solid tumor samples available for retrospective studies being archived as formalin-fixed paraffin-embedded (FFPE) specimens causing the nucleic acids to be highly degraded. Furthermore, stably expressed reference genes for normalization of gene expression data using reverse transcriptase quantitative PCR (RT-qPCR) have not been identified for combined analysis of primary lung tumors and the tissues whereto the cancer metastasize. Using an optimized RT-qPCR workflow we have analyzed the expression of 23 candidate reference genes in a total of 54 FFPE specimens derived from primary Non-Small Cell Lung Cancer tumors, brain metastases, and lymph node metastases as well as normal lung, lymph node, and brain tissues. We show that every aspect of the workflow is highly reproducible, and the PUM1, TBP, and IPO8 genes were identified as the most stably expressed reference genes among the candidates, by using the GeNorm and NormFinder software programs. Furthermore, we demonstrate that commonly used reference genes such as ACTB (β-actin), GAPDH, and rRNA18S are less stably expressed in the studied samples. The presented workflow and the identified reference genes may facilitate more reliable gene expression studies in lung cancer using RNA from FFPE tissues.