Meeting men's health needs by improving healthcare service access is a key objective of comprehensive primary health care. The aims of this qualitative study were to explore the perception of nurses in men's health services and to describe men's expectation of the nurse. The comparative component identifies the barriers and facilitators to improved access to health services. A purposive sample of 19 nurses and 20 men was recruited from metropolitan and regional settings in the state of Victoria, Australia, and each participant was interviewed individually or as part of three focus groups. The main findings were: nurses and men were unclear on the role of the nurse in men's health; and health promotion provided by nurses was predominantly opportunistic. Both participant groups indicated barriers to healthcare access related to: the culture and environment in general practice; limitation of Australia's Medicare healthcare financing system; out-of-pocket costs, waiting time and lack of extended hours; and men not wanting to be perceived as complainers. Facilitators related to: positive inter-professional relations; effective communication; personal qualities; and level of preparedness of nurse education. The findings demonstrate a need for the role to be better understood by both men and nurses in order to develop alternative approaches to meeting men's healthcare needs.