Cancer research has devoted most of its energy over the past decades on unraveling the control mechanisms within tumor cells that govern its behavior. From this we know that the onset of cancer is the result of cumulative genetic mutations and epigenetic alterations in tumor cells leading to an unregulated cell cycle, unlimited replicative potential and the possibility for tissue invasion and metastasis. Until recently it was often thought that tumors are more or less undetected or tolerated by the patient's immune system causing the neoplastic cells to divide and spread without resistance. However, it is without any doubt that the tumor environment contains a wide variety of recruited host immune cells. These tumor infiltrating immune cells influence anti-tumor responses in opposing ways and emerges as a critical regulator of tumor growth. Here we provide a summary of the relevant immunological cell types and their complex and dynamic roles within an established tumor microenvironment. For this, we focus on both the systemic compartment as well as the local presence within the tumor microenvironment of late-stage non-small cell lung cancer (NSCLC), admitting that this multifaceted cellular composition will be different from earlier stages of the disease, between NSCLC patients. Understanding the paradoxical role that the immune system plays in cancer and increasing options for their modulation may alter the odds in favor of a more effective anti-tumor immune response. We predict that the future standard of care of lung cancer will involve patient-tailor-made combination therapies that associate (traditional) chemotherapeutic drugs and biologicals with immune modulating agents and in this way complement the therapeutic armamentarium for this disease.