Governance is central to the sustainable development of tourism through policy formulation, implementation and regulation of stakeholders' activities. This paper examines the challenges of and strategies for enhancing regional tourism governance in Anambra and Enugu States of Southeastern Nigeria. Data were collected through ethnographic fieldwork conducted with key stakeholders (tourism officials, traditional rulers, chief priests, men, women and youth leaders) and analysed using thematic analysis to identify themes reflecting their perceptions for strengthening tourism governance. The results revealed that governance was ineffective because of the government's insincerity and failed promises, absence of tourism professionals and poor private-public partnership. This paper concludes that sustained tourism development requires robust and honest government oversight to address these challenges.