Given a graph G=(V,E), a (d,k)-coloring is an assignment of a color from {1, 2, ..., k} to each vertex of V such that any two vertices within distance d of each other are assigned different colors. We determine the complexity of the (d,k)-coloring problem for all d and k, and enumerate some interesting properties of (d,k)-colorable graphs. Our main result is the discovery of a dichotomy between polynomial and NP-hard instances; for fixed d greater than or equal to 2, the distance coloring problem is polynomial time for k less than or equal to 3d/2 and NP-hard for k greater than 3d/2.