Primary care-related emergency department (PCR-ED) utilization, including for conditions that are preventable or treatable with appropriate primary care, is associated with decreased efficiency of and increased costs to the health system. Many PCR-ED users experience actual or perceived problems accessing appropriate, ongoing sources of medical care. Patient navigation, an intervention used most often in the cancer care continuum, may help to address these barriers among medically underserved populations, such as those who are low income, uninsured, publicly insured, or recent U.S. immigrants. We examined a patient navigation program designed to promote appropriate primary care utilization and prevent or reduce PCR-ED use at Memorial Hermann Health System in Houston, Texas. The intervention is facilitated by bilingual, state-certified community health workers (CHWs) who are trained in peer-to-peer counseling and connect medically underserved patients with medical homes and related support services. The CHWs provide education about the importance of primary care, assist with appointment scheduling, and follow up with patients to monitor and address additional barriers. Our study found that the patient navigation intervention was associated with decreased odds of returning to the ED among less frequent PCR-ED users. Among patients who returned to the ED for PCR reasons, the pre/post mean visits declined significantly over a 12-month pre/post-observation period but not over a 24-month period. The savings associated with reduced PCR-ED visits were greater than the cost to implement the navigation program. Our findings suggest that an ED-based patient navigation program led by CHWs should be further evaluated as a tool to help reduce PCR-ED visits among vulnerable populations.