In this paper, we discuss the solution of an Inverse Eigenvalue Complementarity Problem. Two nonlinear formulations are presented for this problem. A necessary and sufficient condition for a stationary point of the first of these formulations to be a solution of the problem is established. On the other hand, to assure global convergence to a solution of this problem when it exists, an enumerative algorithm is designed by exploiting the structure of the second formulation. The use of additional implied constraints for enhancing the efficiency of the algorithm is also discussed. Computational results are provided to highlight the performance of the algorithm.