This paper presents some new heuristics based on variable neighborhood search to solve the vertex weighted k-cardinality tree problem. An efficient local search procedure is also developed for use within these heuristics. Our computational results demonstrate that the new heuristics substantially outperform the state-of-the-art methodologies, including a Tabu search and genetic algorithm recently proposed in the literature. We also show that a decomposition approach is best for larger problem sizes than previously investigated. Thus, our findings advance in a significant way the capacity to solve this important class of problems.