We introduce a natural-valued complexity c(X) for pairs X=(M,L), where M is a closed orientable 3-manifold and L is a link contained in M. The definition employs simple spines, but for well-behaved X's we show that c(X) equals the minimal number of tetrahedra in a triangulation of M containing L in its 1-skeleton. Slightly adapting Matveev's recent theory of roots for graphs, we carefully analyze the behaviour of c under connected sum away from and along the link. We show in particular that c is almost always additive, describing in detail the circumstances under which it is not. To do so we introduce a certain (0,2)-root for a pair X, we show that it is well-defined, and we prove that X has the same complexity as its (0,2)-root. We then consider, for links in the 3-sphere, the relations of c with the crossing number and with the hyperbolic volume of the exterior, establishing various upper and lower bounds. We also specialize our analysis to certain infinite families of links, providing rather accurate asymptotic estimates.