Summary: The minimum weighted $k$-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly $k$ edges whose sum of weights is minimum. For this $NP$-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.