Background: Specialist palliative care improves quality of life (QOL), symptom burden, and may prolong survival among patients with advanced lung cancer. Previous trials focused on advanced disease, and less is known about patients across a broad range of stages. Objective: We sought to assess the effect of a nurse-led telephone-based primary palliative care intervention that focused on patients across a broad range of stages. Design, Setting, and Participants: We conducted a multisite randomized controlled trial in the United States involving patients diagnosed within two months with any stage or histology of lung cancer to compare the effects of a telephone-based palliative care intervention delivered by registered nurses trained in primary palliative care versus usual care. Main Outcomes and Measures: The primary outcome was the Functional Assessment of Cancer Therapy-Lung Scale Total Outcome Index (FACT-L TOI), which measures QOL and symptoms. We estimated having 80% power to detect a 5-point change from baseline to three months. Secondary outcome was a change in satisfaction of care, measured by the FAMCARE-P13. Results: A total of 151 patients were enrolled over 30 months. Patients were, on average, male (98%), age 70 years, White (85%), and 36% diagnosed with stage I-II, and 64% had stage III-IV. In comparison to usual care, patients in the nurse-led intervention did not report improvement in QOL from baseline to three months follow-up or demonstrate differences in treatment effect by site or cancer stage: FACT-L TOI 1.03 (95% confidence interval [CI]: -3.98 to 6.04). Satisfaction with care did not significantly improve: 0.66 (95% CI: -2.01 to 3.33). Conclusions: Among patients with newly diagnosed lung cancer, a nurse-led, primary palliative care intervention did not significantly improve QOL, symptom burden, or satisfaction of care. In contrast to several clinical trials demonstrating the effectiveness of delivering specialty palliative care with disease-modifying treatments on QOL among patients with advanced lung cancer, this intervention did not significantly improve QOL among patients with any stage lung cancer. Future research should identify which specific components of primary palliative care improve outcomes for patients newly diagnosed with lung cancer.