We present a novel and computationally simple solution to the problem of determining the number of exponentials in a given time-series, which is applicable to both white and colored noise. The solution is based on a novel and non-asymptotic goodness-of-fit metric, referred to as invariant-signal-subspace matching (ISSM). This metric is aimed at matching pairs of signal-subspaces, created by exploiting the shift-invariance property of the Hankel data-matrix. A pair of such subspaces, together with their corresponding projection matrices, is created for every hypothesized number of exponentials, and the number of exponentials is then determined as that for which the distance between the pair of projection matrices is minimized. We prove the consistency of this criterion for the high signal-to-noise-ratio limit and also prove it for the large-sample limit, conditioned on the noise being white. We also extend this criterion to include multiple pairs of invariant subspace, readily created from the Hankel data-matrix, thus enabling to improve its performance at a slight increase in its computational load. Simulation results, demonstrating the superior performance of the solution over the existing solutions, for both colored and white noise, are included.