Accurate diagnosis of histological type is important for therapy selection in lung cancer. Immunohistochemical (IHC) and histochemical stains are often used to complement morphology for definite diagnosis and are incorporated in the WHO classification. Our main aim was to compare different mucin stains and assess their value in relation to common IHC analyses in lung cancer diagnostics. Using tissue microarrays from 657 surgically treated primary lung cancers, we evaluated the mucin stains periodic acid-Schiff with diastase (PASD), alcian blue-periodic acid-Schiff (ABPAS) and mucicarmine, and compared with the IHC markers p40, p63, cytokeratin 5, thyroid transcription factor 1 (TTF-1), napsin A and cytokeratin 7. Ten or more cytoplasmic mucin inclusions in a tissue microarray core were seen in 51%, 48% and 31% of the 416 adenocarcinomas and 3%, 4% and 0.5% of the 194 squamous cell carcinomas with PASD, ABPAS and mucicarmine, respectively. Diagnostic pitfalls, such as entrapped benign epithelium, apoptotic/necrotic cells and glycogen, partly differed for the mucin stains. TTF-1 and napsin A IHC stainings had similar specificity but better sensitivity for adenocarcinoma than the mucin stains, but addition of PASD or ABPAS identified more tumors as adenocarcinomas (n = 8 and n = 10, respectively) than napsin A (n = 1) in cases with solid growth that were negative for TTF-1 and p40. We conclude that PASD and ABPAS have similar diagnostic performance and that these markers are of value in poorly differentiated cases. However, morphology and TTF-1 and p40 IHC staining is sufficient for correct diagnosis in most non-small cell lung cancers.