For an integer d >= 3, let k = k_d the smallest integer k such that d < 2k log k. We show that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2. Moreover, if (2k-1) log k <= d <= 2k log k then the chromatic number is either k+1 or k+2.