The problem of generating a uniformly, or almost uniformly, random proper q-coloring of a given graph in polynomial time is an interesting and challenging sampling problem that has been widely studied in the sequential setting. Recently there has been interest in distributed algorithms for the problem, where the goal is to get parallel speedup, so that the running time is polylogarithmic in n. Existing approaches converge in logarithmic time but with a small increase in the number of colors required, which, for most of the sequential results, is already more than the maximum degree of the graph. We study the problem of distributed sampling of q-colorings in the special case where the graph is a tree. Regardless of the maximum degree of the tree, which may be as large as \(\varOmega (n)\) , we allow the number of available colors, q, to be as small as three. We present a distributed CONGEST algorithm that produces an almost uniform proper q-coloring of the tree. Additionally, if the tree is rooted, a modification of our algorithm produces a uniformly random proper q-coloring. Both algorithms succeed with probability 1, and have a running time that is \(O(\log ^2 n)\) with high probability.