Background: Although low-dose computed tomography (LDCT)-based lung cancer screening (LCS) can decrease lung cancer mortality in high-risk individuals, it may be a complex and time-intensive process that poses challenges to patients, particularly those from minority, under- and uninsured populations. We conducted a pragmatic randomized controlled trial of telephone-based navigation for LCS within an integrated, urban safety-net healthcare system (Parkland Health, Dallas, Texas). Methods: Patients eligible for LCS based on United States Preventive Services Task Force 2013 Guidelines were randomized (1:1) to usual care with or without phone-based navigation. Following a structured protocol, navigators made systemic contact with patients to provide appointment reminders, share information and resources, assess barriers to LCS, and address smoking cessation. The primary endpoint was completion of the first three consecutive steps (eg, 3 annual LDCTs or LDCT, other imaging, biopsy) in a patient’s LCS process. We also explored differences in completion of LCS steps in navigation and usual care groups according to patient characteristics using chi-square test. Results: Patients (n=447) were randomized to phone-based navigation (n=225) or usual care (n=222) between February 2017 and February 2019. Mean patient age was 62 years, 46% were female, and 69% were racial-ethnic minorities. There was no significant difference in completion of the first three steps of the LCS algorithm (12 vs. 9%; P=0.3) between arms. Completion of LCS steps was not impacted by navigation among different subgroups, including age (<65 vs. ≥65 years), gender (male vs. female), race/ethnicity (non-hispanic white vs. racial minorities), and comorbidity status (Charlson Comorbidity Index <5 vs. ≥5). A key reason for step non-completion was lack of order placement. In the navigation arm, 368 of expected 675 steps (55%) were ordered, and in the usual care arm, 344 of expected 666 steps (52%) were ordered. Despite low three-step completion rates overall, the majority (>75%) of LCS algorithm steps were completed when ordered by their clinical team(Table). In exploratory univariable analysis, completion rates for ordered steps were 86% for navigation and 79% for usual care (P=0.03). Conclusions: In this study, lack of order placement was a key reason for incomplete LCS steps. When orders were placed, navigated patients had higher rates of completion. Clinical team education and enhanced EHR processes to simplify order placement, coupled with patient navigation, may increase LCS uptake and completion in safety-net healthcare systems. Clinical trial information: NCT02758054.