Summary: We study the evolution of the chromatic number of a random intersection graph and show that, in a certain range of parameters, these random graphs can be colored optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.