BACKGROUND: The high rates of relapse that tend to occur after short-term behavioral interventions indicate the need for maintenance programs that promote long-term adherence to new behavior patterns. Computer-tailored health messages that are mailed to participants or given in brief telephone calls offer an innovative and time-efficient alternative to ongoing face-to-face contact with healthcare providers. METHODS: Following a 1-year behavior change program, 22 North Carolina health departments were randomly assigned to a follow-up intervention or control condition. Data were collected from 1999 to 2001 by telephone-administered surveys at preintervention and postintervention for 511 low-income, midlife adult women enrolled in the Well-Integrated Screening and Evaluation for Women Across the Nation (WISEWOMAN) program at local North Carolina health departments. During the year after the behavior change program, intervention participants were mailed six sets of computer-tailored health messages and received two computer-tailored telephone counseling sessions. Main outcomes of dietary and physical activity behaviors, beliefs, and attitudes were measured. RESULTS: Intervention participants were more likely to move forward into more advanced stages of physical activity change (p = 0.02); control participants were more likely to increase their level of dietary social support at follow-up (p = 0.05). Both groups maintained low levels of reported saturated fat and cholesterol intake at follow-up. No changes were seen in physical activity in either group. CONCLUSIONS: Mailed computer-tailored health messages and telephone counseling calls favorably modified forward physical activity stage movement but did not appreciably affect any other psychosocial or behavioral outcomes.