Members of vulnerable populations have heightened needs for health services. One advantage of integrating health risk assessment and referrals into social service assistance systems such as 2-1-1 is that such systems help callers resolve problems in other areas (e.g., housing). Callers to 2-1-1 in Missouri (N = 1,090) with at least one behavioral risk factor or cancer screening need were randomly assigned to one of three health referral interventions: verbal referrals only, verbal referrals + a tailored mailed reminder, or verbal referrals + telephone health navigator. After 1 month, we assessed whether the nonhealth problems that prompted the 2-1-1 call had been resolved. Logistic regression estimated effects of having the problem resolved on calling a health referral. Callers were predominantly female (85%) and had a high school education or less (61%); nearly half (47%) had incomes under $10,000. The most common service requests were for utility assistance (35%), home/family problems (23%), and rent/mortgage assistance (12%). At follow-up, 38% of callers reported that all problems prompting their 2-1-1 call had been resolved, and 24% reported calling a health referral. Resolving all problems prompting the 2-1-1 call was associated with a higher odds of contacting a health referral (odds ratio = 1.44, 95% confidence interval [1.02, 2.05]) compared to people whose problems were not resolved. Multifaceted interventions that help meet non-health-related needs and provide support in reaching health-related goals may promote health in vulnerable populations.