We develop and analyze parallelization strategies for the Variable Neighborhood Search (VNS) meta-heuristic applied to the p-median problem. The strategy we propose combines multi-thread cooperation parallelization principles to the simplicity of the original VNS ideas. Extensive experimentations have been conducted on the classical TSPLIB benchmark problem instances with up to 11948 customers and 1000 medians. We report excellent speedup factors and solutions that are qualitatively comparable to the best published results.