The ability of early lung cancer diagnosis is an unmet need in clinical practice. Lung cancer metabolomic analyses conducted so far have demonstrated several abnormalities in cancer lipid profile providing a rationale for further study of blood lipidome of the patients. In the present research, we performed a targeted lipidome screening to select molecules that show promise for early lung cancer detection. The study was conducted on serum samples collected from newly diagnosed, stage I non-small cell lung cancer (NSCLC) patients and non-cancer controls. A high-throughput mass spectrometry-based platform with confirmed interlaboratory reproducibility was used. The analyzed profile consisted of acylcarnitines, sphingomyelins, phosphatidylcholines and lysophosphatidylcholines. Among the assayed lipid species, the significant differences between NSCLC and non-cancer subjects were observed in the group of phosphatidylcholines (PC) and lysophosphatidylcholines (lysoPC), especially in the levels of lysoPC a C26:0; lysoPC a C26:1; PC aa C42:4; and PC aa C34:4. The metabolites mentioned above were used to create a multivariate classification model, which reliability was proved by permutation tests as well as external validation. Our study indicated choline-containing phospholipids as potential lung cancer markers. Further investigations of phospholipidome are crucial to better describe the shifts in metabolite composition occurring in lung cancer patients.