For an ordered k-decomposition D = {G1, G2, . . . , Gk} of a connected graph G and an edge e of G, the D-code of e is the k-tuple cD(e) = (d(e, G1), d(e, G2), . . . , d(e, Gk)), where d(e, Gi) is the distance from e to Gi . A decomposition D is resolving if every two distinct edges of G have distinct D-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dimd(G). A resolving decomposition D of G is connected if each Gi is connected for 1 ≤ i ≤ k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 ≤ dimd(G) ≤ cd(G) ≤ m for every connected graph G of size m ≥ 2. All nontrivial connected graphs with connected decomposition number 2 or m are characterized. We provide bounds for the connected decomposition number of a connected graph in terms of its size, diameter, girth, and other parameters. A formula for the connected decomposition number of a nonpath tree is established. It is shown that, for every pair a, b of integers with 3 ≤ a ≤ b, there exists a connected graph G with dimd(G) = a and cd(G) = b.