Minimum k-cardinality tree problem on graph G consists in finding a subtree of G with exactly k edges whose sum of weights is minimum. In this paper we propose Variable neighborhood search heuristic for solving it. We also analyze different shaking strategies and their influence on the final solution. New methods are compared favourably with other heuristics from the literature.