Let k ∈ N and c ∈ Zk. A graph G is said to be c-sum k-magic if there is a labeling ` : E(G) → Zk \ {0} such that P u∈N(v) `(uv) ≡ c (mod k) for every vertex v of G, where N(v) is the neighborhood of v in G. We say that G is completely k-magic whenever it is c-sum k-magic for every c ∈ Zk. In this paper, we characterize all completely k-magic regular graphs.