  The integral circulant graph $ICG_n (D)$ has the vertex set $Z_n = \{0, 1, 2,
\ldots, n - 1\}$, where vertices $a$ and $b$ are adjacent if $\gcd(a-b,n)\in
D$, with $D \subseteq \{d : d \mid n,\ 1\leq d<n\}$. In this paper, we
establish that the minimal value of the least eigenvalues (minimal least
eigenvalue) of integral circulant graphs $ICG_n(D)$, given an order $n$ with
its prime factorization $p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, is equal to
$-\frac{n}{p_1}$. Moreover, we show that the minimal least eigenvalue of
connected integral circulant graphs $ICG_n(D)$ of order $n$ whose complements
are also connected is equal to $-\frac{n}{p_1}+p_1^{\alpha_1-1}$. Finally, we
determine the second minimal eigenvalue among all least eigenvalues within the
class of connected integral circulant graphs of a prescribed order $n$ and show
it to be equal to $-\frac{n}{p_1}+p_1-1$ or $-\frac{n}{p_1}+1$, depending on
whether $\alpha_1>1$ or not, respectively. In all the aforementioned tasks, we
provide a complete characterization of graphs whose spectra contain these
determined minimal least eigenvalues.

Combinatorics