Successful therapy of the non-small cell lung carcinoma (NSCLC) depends on its early detection, and non-invasive detection methods are preferred. As plasma proteins are modified by N-linked glycosylation, we tested the importance of the N-glycan profile in diagnosing and prognosticating NSCLC. We analysed desialylated plasma samples from 75 NSCLC patients, and 71 healthy individuals by the high-throughput DNA sequencer-based carbohydrate analytical profiling technique. We detected alterations in the levels of several N-glycans in NSCLC patients. Total α-1,6-core fucosylated biantennaries (NGA2F, NG1A2F, NA2F) and total bisecting α-1,6-core fucosylated biantennaries (NGA2FB, NA2FB) were reduced in NSCLC patients, whereas the branching α-1,3-fucosylated triantennary N-glycan (NA3FB) was increased. Best diagnostic accuracy was identified for NG1A2F. NSCLC patients with TNM stage I stage did not show further differences, but patients with higher stages did (TNM II to IV). Those patients additionally had a reduced level in the α-1,6-core fucosylated structure NA2F with parallel increase in the non-fucosylated structure NA2. In this regard, NSCLC patients with a relatively low amount of NA2 per NA2F had a better three-year survival than patients with high amount. NSCLC patients show an altered N-glycan profile of plasma proteins that may be regarded as a supportive tool for cancer diagnosis.