About three million Muslims are traveling annually to Makkah in Saudi Arabia to perform the rituals of Hajj (i.e. the pilgrimage), the fifth pillar of Islam. It requires the pilgrims to move to several holy sites while performing the Hajj ritual, including Mina, Arafat, and Muzdalifah sites. However, pilgrims spend most of their time in prepared tent-camps at the Mina site during the days of Hajj. Among the challenges that the organizers face in the Hajj is the distribution of pilgrims over the camps of Mina while considering a range of constraints, which is considered a real-world optimization problem. This paper introduces a hyper-heuristic approach to optimize the distribution process of pilgrims over Mina tent-camps in an efficient manner, named the hyper-heuristic Mina tents distribution algorithm (HyMTDA). The proposed algorithm, iteratively, selects one heuristic among four predefined low-level heuristics to produce a new solution; thereafter the late move acceptance strategy is applied as a judgment to accept or reject the new solution. The performed simulations show that the proposed HyMTDA can effectively explore the search space and avoid falling into local minima during the iterations process. Moreover, comparisons show that HyMTDA outperforms other heuristic algorithms in the literature in terms of solution quality and convergence rate.