The Minimum k-Dominating Set (MKDS) is a hard combinatorial optimization problem with real-world applications ranging from communication networks to facility location problems. Given a graph, the goal involves finding a subset of vertices with minimum cardinality such that every vertex not in the subset is adjacent to at least k dominant vertices. Due to its NP-Hardness, the MKDS problem is tackled from a metaheuristic perspective, proposing a Variable Neighborhood Search (VNS). The different decisions taken are validated through computational experiments which includes a competitive testing with the best method in the literature, a Restart Local Search with Relaxed Configuration Checking. The proposed VNS obtains competitive results (an average deviation of 0.71%) showing potential for future works.