We present a combinatorial proof of two fundamental composition identities associated with Chebyshev polynomials. Namely, for all m, n >= 0, T(m)(T(n)(x)) = T(mn)(x) and U(m-1) (T(n)(x))U(n-1)(x) = U(mn-1)(x). (C) 2010 Elsevier B.V. All rights reserved.