In this paper we consider the k-minimum spanning tree problem that generalizes the famous minimum weight spanning tree problem which is one of the major classes of combinatorial optimization problems. We propose an approach for solving this problem based on the Simulated Annealing algorithm. The performance of the proposed method is compared with existing metaheuristics using the well-known benchmark instances KCTLIB.