A C*-algebra satisfies the Universal Coefficient Theorem (UCT) of Rosenberg and Schochet if it is equivalent in Kasparov’s KK-theory to a commutative C*-algebra. This paper is motivated by the problem of establishing the range of validity of the UCT, and in particular, whether the UCT holds for all nuclear C*-algebras. We introduce the idea of a C*-algebra that “decomposes” over a class 𝒞 of C*-algebras. Roughly, this means that locally there are approximately central elements that approximately cut the C*-algebra into two C∗-subalgebras from 𝒞 that have well-behaved intersection. We show that if a C*-algebra decomposes over the class of nuclear, UCT C∗-algebras, then it satisfies the UCT. The argument is based on a Mayer–Vietoris principle in the framework of controlled KK-theory; the latter was introduced by the authors in an earlier work. Nuclearity is used via Kasparov’s Hilbert module version of Voiculescu’s theorem, and Haagerup’s theorem that nuclear C*-algebras are amenable. We say that a C*-algebra has finite complexity if it is in the smallest class of C*-algebras containing the finitedimensional C*-algebras, and closed under decomposability; our main result implies that all C*-algebras in this class satisfy the UCT. The class of C*-algebras with finite complexity is large, and comes with an ordinal-number invariant measuring the complexity level. We conjecture that a C*-algebra of finite nuclear dimension and real rank zero has finite complexity; this (and several other related conjectures) would imply the UCT for all separable nuclear C*-algebras. We also give new local formulations of the UCT, and some other necessary and sufficient conditions for the UCT to hold for all nuclear C*-algebras.