Let M be a (possibly non-orientable) compact 3-manifold with (possibly empty) boundary consisting of tori and Klein bottles. Let X ⊂ ∂ M be a trivalent graph such that ∂ M \ X is a union of one disc for each component of ∂ M . Building on previous work of Matveev, we deﬁne for the pair (M, X) a complexity c(M, X) ∈ N and show that, when M is closed, irreducible and P2-irreducible, c(M, ∅) is the minimal number of tetrahedra in a triangulation of M . Moreover c is additive under connected sum, and, given any n >= 0, there are only ﬁnitely many irreducible and P2 -irreducible closed manifolds having complexity up to n. We prove that every irreducible and P2 -irreducible pair (M, X) has a ﬁnite splitting along tori and Klein bottles into pairs having the same properties, and complexity is additive on this splitting. As opposed to the JSJ decomposition, our splitting is not canonical, but it involves much easier blocks than all Seifert and simple manifolds. In particular, most Seifert and hyperbolic manifolds appear to have non- trivial splitting. In addition, a given set of blocks can be combined to give only a ﬁnite number of pairs (M, X). Our splitting theorem provides the theoretical background for an algorithm which classiﬁes 3-manifolds of any given complexity. This algorithm has been already implemented and proved eﬀective in the orientable case for complexity up to 9.