Consider a set L of potential locations for p facilities and a set U of locations of given users. The p-median problem is to locate simultaneously the p facilities at locations of L in order to minimize the total transportation cost for satisfying the demand of the users, each supplied from its closest facility. This model is a basic one in location theory and can also be interpreted in terms of cluster analysis (locations of users are then replaced by points in a given space). We propose several new Variable Neighbourhood Search heuristics for the p-Median problem and compare them with Greedy plus Interchange, and two Tabu Search heuristics.