Programs and initiatives addressing American Indian and Alaska Native (AI/AN) health disparities have recently shifted to better understanding, identifying and promoting successful programs designed to improve the health of AI/AN men. We sought to describe the priorities of front-line leadership of Indian Health Service, Tribal, and Urban (ITU) health programs, especially in relation to men’s health. We also sought to ascertain how potential future partners in men’s health research perceive the priorities established by the Indian Health Care Improvement Act (IHCIA). We surveyed directors of Indian Health Service, tribally operated facilities/programs, and Urban Indian clinics (I/T/U’s) on the relative importance of a range of health topics and issues and whether gender-based strategies were crucial to implementation. I/T/U directors identified diabetes (68%), alcohol and substance abuse (61%), mental/behavioral health (56%), obesity (53%) and addiction (40%) as the highest priority issues affecting both men and women. Only seven directors (6%) selected “men’s health” as a stand-alone priority. However, 80% said gender-tailored implementation was at least somewhat important for three or more of the priorities they selected. While neither men’s nor women’s health was identified as a standalone concern, health directors identified gender tailoring as a useful strategy for addressing many health issues.