This paper presents an application of tree-seed algorithm (TSA) -which is based on the relation between trees and their seeds- on the P-median benchmark problems. To the best knowledge of the authors, this is the first study which applies TSA to the P-median problem. In this paper, different P-median problem instances are generated to show the applicability of the TSA. The experimental results are compared with the optimal results obtained by GAMS-CPLEX. Also, TSA is applied on data sets from OR-Library, and then the obtained and known optimal results are compared. The comparisons demonstrate that the TSA can find optimal and near-optimal values for the small and medium-sized problems, respectively.