(1) Background: The main objectives of our study are (i) to determine the prevalence of NTRK (neurotrophic tyrosine kinase) fusions in a routine diagnostic setting in NSCLC (non-small cell lung cancer) and (ii) to investigate the feasibility of screening approaches including immunohistochemistry (IHC) as a first-line test accompanied by fluorescence in situ hybridization (FISH) and RNA-(ribonucleic acid-)based next-generation sequencing (RNA-NGS). (2) Methods: A total of 1068 unselected consecutive patients with NSCLC were screened in two scenarios, either with initial IHC followed by RNA-NGS (n = 973) or direct FISH testing (n = 95). (3) Results: One hundred and thirty-three patients (14.8%) were IHC positive; consecutive RNA-NGS testing revealed two patients (0.2%) with NTRK fusions (NTRK1-EPS15 (epidermal growth factor receptor pathway substrate 15) and NTRK1-SQSTM1 (sequestosome 1)). Positive RNA-NGS was confirmed by FISH, and NTRK-positive patients benefited from targeted treatment. All patients with direct FISH testing were negative. RNA-NGS- or FISH-positive results were mutually exclusive with alterations in EGFR (epidermal growth factor receptor), ALK (anaplastic lymphoma kinase), ROS1 (ROS proto-oncogene 1), BRAF (proto-oncogene B-Raf), RET (rearranged during transfection) or KRAS (kirsten rat sarcoma viral oncogene). Excluding patients with one of these alterations raised the prevalence of NTRK-fusion positivity among panTrk-(tropomyosin receptor kinase-) IHC positive samples to 30.5%. (4) Conclusions: NTRK fusion-positive lung cancers are exceedingly rare and account for less than 1% of patients in unselected all-comer populations. Both RNA-NGS and FISH are suitable to determine clinically relevant NTRK fusions in a real-world setting. We suggest including panTrk-IHC in a diagnostic workflow followed by RNA-NGS. Excluding patients with concurrent molecular alterations to EGFR/ALK/ROS1/BRAF/RET or KRAS might narrow the target population.