The global minimum structures for Li(x)CoO(2) compositions where 0 ≤ x ≤ 1 were probed by using a hybrid evolutionary algorithm with an underlying ab initio structural relaxation scheme. The method successfully predicted experimentally observed variants of layered configurations at various degrees of lithiation and the spinel (Fd3[combining macron]m) phase at x = 1/2. New low-energy non-layered host structures at x < 1/2 were also revealed. These structures can be formed from the usual layered configuration through coherent stacking faults along the c-axis and the migration of Co ions into the Li-poor intercalation layer.