Introduction to The Problem: Labuan Bajo is considered one of the potential destinations for the development of halal tourism in Indonesia. However, the predominance of a non-Muslim population in the region presents a distinctive challenge in the implementation and promotion of halal tourism practices. Purpose/Objective Study: Explore the needs of Muslim travelers who visit the Super Priority Destination of Labuan Bajo, one of the tourist destinations where most population is non-Muslim. Design/Methodology/Approach: The approach used is qualitative, with data collected through in-depth interviews with Muslim Traveler informants who have visited Labuan Bajo. The in-depth interview questions are based on the extension of the theory of travel. Findings: The research results show that the main motivations for Muslim travelers visiting this place are recreation and work, where natural beauty and ease of access are the main factors attracting Muslim tourists to visit this place. However, there are still many challenges that need to be addressed, such as the limited availability of prayer facilities in some island destinations, the lack of halal-certified food options, and the insufficient communication between tour providers and tourists. This study concludes that Labuan Bajo is a Muslim-friendly destination, but the improvement of worship facilities and halal food must be optimized. This research is expected to serve as a foundation for the development of halal tourism in predominantly non-Muslim destinations that are inclusive and sustainable.