This work addresses the Ordered Median Tree Location Problem (OMT), a combinatorial optimization problem recently introduced that involves the p-median and minimum spanning tree problems. The OMT seeks to locate $p$ facilities and connect them via a tree structure to serve a set of customers, minimizing ordered weighted customer assignments and tree connection costs. To efficiently solve this problem, we propose a Greedy Randomized Adaptive Search Procedure (GRASP), incorporating a swap-based local search. Computational experiments demonstrate that the proposed metaheuristic significantly outperforms the state-of-the-art exact formulation, finding the best-known solution for all instances with low computational cost.