Thallium compounds have appeared as a new class of advanced thermoelectric (TE) materials owing to their extremely low lattice thermal conductivity. Using a first-principles approach and Boltzmann transport theories, we investigate the electronic and phonon transport properties of a ternary thallium telluride, TlInTe2. Unlike the Bi2Te3 and PbTe used in current TE devices, a multi-valley band structure with intrinsic degeneracy is obtained for TlInTe2, which contributes to its high Seebeck coefficient and relatively high power factor. Also, because of its weak bonding stiffness and strong phonon anharmonicity, TlInTe2 has an extremely low lattice thermal conductivity of about 0.37 W m-1 K-1 at room temperature, which is almost one third of the values for Bi2Te3 and PbTe. Consequently, competitive ZT values of 1.78 and 1.84 are obtained at 300 K for p- and n-doped TlInTe2, respectively, indicating that thallium compounds are promising TE materials for practical applications.