Intimate partner violence (IPV) is a common complex social and public health problem. Interventions for IPV male perpetrators are an essential component of an early and effective response. Yet little is known about how to engage men in interventions for help-seeking. Using the theory of planned behavior (TPB), we explored men's perceptions of seeking help for an unhealthy relationship and how they could be supported to recognize their behavior and undertake change at an early stage. We recruited 23 men who were currently attending a men's behavior change program in Australia to take part in focus groups. These were recorded, transcribed, and thematically analyzed. The TPB concepts of behavioral beliefs, perceived control, and subjective norms were found throughout the data. Behavioral beliefs covered four subthemes: self-awareness, self-reflection and agency, the influence of others to change, and needing the right message in the right place. Perceived control was connected to these men's understandings of what it means to be a man. Subjective norms were rarely raised, but there was some indication that men's perceptions of societal norms about men as violent influenced a perceived lack of agency to change behavior. Our findings highlight the complexity of, and challenges in, engaging men who may use violence before they reach crisis point and justice intervenes. Despite this, participating men could find acceptable an appropriately developed and easy-to-access intervention that enhances recognition of behaviors and provides links to supports. Health professionals or researchers developing early interventions targeting these men need to take the engagement challenges into account.