Lung cancer is the major human malignancy, accounting for 30% of all cancer-related deaths worldwide. Poor survival of lung cancer patients, together with late diagnosis and resistance to classic chemotherapy, highlights the need for identification of new biomarkers for early detection. Among different cancer biomarkers, small non-coding RNAs called microRNAs (miRNAs) are considered the most promising, owing to their remarkable stability, their cancer-type specificity, and their presence in body fluids. However, results of multiple previous attempts to identify circulating miRNAs specific for lung cancer are inconsistent, likely due to two main reasons: prominent variability in blood miRNA content among individuals and difficulties in distinguishing tumor-relevant miRNAs in the blood from their non-tumor counterparts. To overcome these impediments, we compared circulating miRNA profiles in patients with lung squamous cell carcinoma (SCC) before and after tumor removal, assuming that the levels of all tumor-relevant miRNAs would drop after the surgery. Our results revealed a specific panel of the miRNAs (miR-205, -19a, -19b, -30b, and -20a) whose levels decreased strikingly in the blood of patients after lung SCC surgery. Interestingly, miRNA profiling of plasma fractions of lung SCC patients revealed high levels of these miRNA species in tumor-specific exosomes; additionally, some of these miRNAs were also found to be selectively secreted to the medium by cultivated lung cancer cells. These results strengthen the notion that tumor cells secrete miRNA-containing exosomes into circulation, and that miRNA profiling of the exosomal plasma fraction may reveal powerful cancer biomarkers.