OBJECTIVES: We pretested interventions derived from different domains of behavior change theory to determine their effectiveness at increasing hand washing with soap in a natural setting. METHODS: We installed wireless devices in highway service station restrooms to record entry and soap use. Two text-only messages for each of 7 psychological domains were compared for their effect on soap-use rates. We collected data on nearly 200 000 restroom uses. RESULTS: The knowledge activation domain was most effective for women, with a relative increase in soap use of 9.4% compared with the control condition (P = .001). For men, disgust was the most effective, increasing soap use by 9.8% (P = .001). Disgust was not significantly better than the control condition for women, nor was knowledge activation for men. Messages based on social norms and social status were effective for both genders. CONCLUSIONS: Our data show that unobtrusive observation of behavior in a natural setting can help identify the most effective interventions for changing behaviors of public health importance. The gender differences we found suggest that public health interventions should target men and women differently.