Abstract In this paper we study the reconstruction of a network topology from the eigenvalues of its Laplacian matrix. We introduce a simple cost function and consider the tabu search combinatorial optimization method, while comparing its performance when reconstructing different categories of networks–random, regular, small-world, scale-free and clustered–from their eigenvalues. We show that this combinatorial optimization method, together with the information contained in the Laplacian spectrum, allows an exact reconstruction of small networks and leads to good approximations in the case of networks with larger orders. We also show that the method can be used to generate a quasi-optimal topology for a network associated to a dynamic process (like in the case of metabolic or protein–protein interaction networks of organisms).