In this paper, we examine the p-median problem from a bi-objective point of view. Since this is a NP-Hard problem, an efficient algorithm based on the Iterated Local Search heuristic (ILS) is proposed to determine non-dominated solutions (an approximation of the Pareto-optimal solutions). ILS is a simple and powerful stochastic method that has shown very good results for a variety of single-objective combinatorial problems. In each component of the ILS, we use the concept of Pareto dominance. An intensification component based on the Path-Relinking is used to improve the quality of the found non-dominated solutions. To test the performance of the proposed algorithm, we develop a Mathematical Programming Algorithm, called c-Constraint, that finds a subset of Pareto-optimal solutions by solving iteratively the mathematical model of the problem with additional constraints. The results show that the proposed approach is able to generate good approximations to the non-dominated frontier of the bi-objective problem efficiently.