In this work, the phase diagram of LixCoO2 is calculated from first principles for x ranging from 0 to 1. Our calculations indicate that there is a tendency for Li ordering at x=1/2 in agreement with experiment [J. N. Reimers and J. R. Dahn, J. Electrochem. Sec. 139, 2091 :1992)]. At low Li concentration, we find that a staged compound is stable in which the Li ions selectively segregate to every other Li plane leaving the remaining Li planes vacant. We do not find the two-phase region observed at high Li concentration and speculate that this two-phase region is caused by the metal-insulator transition that occurs at concentrations slightly below x =1.