This study aimed to clarify genetic and epigenetic alterations that occur during lung carcinogenesis and to design perspective sets of newly identified biomarkers. The original method includes chromosome 3 specific NotI-microarrays containing 180 NotI clones associated with genes for hybridization with 40 paired normal/tumor DNA samples of primary lung tumors: 28 squamous cell carcinomas (SCC) and 12 adenocarcinomas (ADC). The NotI-microarray data were confirmed by qPCR and bisulfite sequencing analyses. Forty-four genes showed methylation and/or deletions in more than 15% of non-small cell lung cancer (NSCLC) samples. In general, SCC samples were more frequently methylated/deleted than ADC. Moreover, the SCC alterations were observed already at stage I of tumor development, whereas in ADC many genes showed tumor progression specific methylation/deletions. Among genes frequently methylated/deleted in NSCLC, only a few were already known tumor suppressor genes: RBSP3 (CTDSPL), VHL and THRB. The RPL32, LOC285205, FGD5 and other genes were previously not shown to be involved in lung carcinogenesis. Ten methylated genes, i.e., IQSEC1, RBSP3, ITGA 9, FOXP1, LRRN1, GNAI2, VHL, FGD5, ALDH1L1 and BCL6 were tested for expression by qPCR and were found downregulated in the majority of cases. Three genes (RBSP3, FBLN2 and ITGA9) demonstrated strong cell growth inhibition activity. A comprehensive statistical analysis suggested the set of 19 gene markers, ANKRD28, BHLHE40, CGGBP1, RBSP3, EPHB1, FGD5, FOXP1, GORASP1/TTC21, IQSEC1, ITGA9, LOC285375, LRRC3B, LRRN1, MITF, NKIRAS1/RPL15, TRH, UBE2E2, VHL, WNT7A, to allow early detection, tumor progression, metastases and to discriminate between SCC and ADC with sensitivity and specificity of 80-100%.