Angiogenesis is a critical event in the development, progression, and spread of various human cancers, including lung cancer. Molecular mechanisms that underlie the complex regulation of angiogenic processes are poorly understood. However, an increasing body of evidence indicates miRNAs as important regulators of tumor angiogenesis. Forceps biopsies were collected from tumor tissue, surrounding tissue, and non-tumor tissue from 50 NSCLC patients. Lung tissue samples from individuals with no clinical evidence of a cancerous disease served as controls. Immunohistochemical staining for Factor VIII was used to evaluate microvessel density (MVD). TaqMan® primer-probe sets were used in quantitative real-time RT-PCR reactions to determine expression levels of let-7b, miR-126, miR-9, and miR-19a. We demonstrated significantly higher MVD and decreased expression levels of let-7b and miR-126 in tumor tissue and surrounding tissue in comparison to corresponding non-tumor tissue or lung tissue from the control group. In addition, no differences in MVD and expression levels of both miRNAs between tumor tissue and surrounding tissue from NSCLC patients were observed. Low expression of both miRNAs correlated with high MVD and worse progression-free survival and overall survival. These observations strongly suggest similar molecular alternations within tumor tissue and surrounding tissue that comprise a specific microenvironment. Low expression of let-7b and miR-126 seems to have a possible anti-angiogenic role in lung tumor tissue and significantly correlates with worse survival outcomes for lung cancer patients. Moreover, the regulation of let-7b and miR-126 expression could have therapeutic potential because it could reduce tumor angiogenesis and therefore suppress tumor growth in lung cancer patients.