  Little Higgs theories are an attempt to address the little hierarchy problem,
i.e., the tension between the naturalness of the electroweak scale and the
precision measurements showing no evidence for new physics up to 5-10 TeV. In
little Higgs theories, the Higgs mass-squareds are protected to the one-loop
order from the quadratic divergence. This allows the cutoff to be raised up to
\~10 TeV, beyond the scales probed by the precision data. However, strong
constraints can still arise from the contributions of the new TeV scale
particles and hence re-introduces the fine-tuning problem. In this paper we
show that a new symmetry, denoted as T-parity, under which all heavy gauge
bosons and scalar triplets are odd, can remove all the tree-level contributions
to the electroweak observables and therefore makes the little Higgs theories
completely natural. The T-parity can be manifestly implemented in a majority of
little Higgs models by following the most general construction of the low
energy effective theory a la Callan, Coleman, Wess and Zumino. In particular,
we discuss in detail how to implement the T-parity in the littlest Higgs model
based on SU(5)/SO(5). The symmetry breaking scale f can be even lower than 500
GeV if the contributions from the unknown UV physics at the cutoff are somewhat
small. The existence of $T$-parity has drastic impacts on the phenomenology of
the little Higgs theories. The T-odd particles need to be pair-produced and
will cascade down to the lightest T-odd particle (LTP) which is stable. A
neutral LTP gives rise to missing energy signals at the colliders which can
mimic supersymmetry. It can also serve as a good dark matter candidate.
