Summary: The location planning of relief distribution centres (DCs) is crucial in humanitarian logistics as it directly influences the disaster response and service to the affected victims. In light of the critical role of facility location in humanitarian logistics planning, the study proposes a two-stage relief distribution location problem. The first stage of the model determines the minimum number of relief DCs, and the second stage find the optimal location of these DCs to minimize the total cost. To address a more realistic situation, restrictions are imposed on the coverage area and capacity of each DCs. In addition, for optimally solving this complex NP-hard problem, a novel two-phase algorithm with exploration and exploitation phase is developed in the paper. The first phase of the algorithm i.e., exploration phase identifies a near-optimal solution while the second phase i.e. exploitation phase enhances the solution quality through a close circular proximity investigation. Furthermore, the comparative analysis of the proposed algorithm with other well-known algorithms such as genetic algorithm, pattern search, fmincon, multistart and hybrid heuristics is also reported and computationally tested from small to large data sets. The results reveal that the proposed two-phase algorithm is more efficient and effective when compared to the conventional metaheuristic methods.