Using an efficient structure search method based on a particle swarm optimization algorithm, we study the structural evolution of solid carbon dioxide (CO2) under high pressure. Our results show that, although it undertakes many structural transitions under pressure, CO2 is quite resistive to structures with C beyond 4-fold coordination. For the first time, we are able to identify two 6-fold structures of solid CO2 with Pbcn and Pa3 symmetries that become stable at pressures close to 1 TPa. Both structures consist of a network of C-O octahedra, showing hypervalence of the central C atoms. The C-O bond length varies from 1.30 to 1.34 �� at the 4-fold to 6-fold transition, close to the C-O distance in the transition state of a corresponding S(N)2 reaction. It has been a longstanding and challenging objective to stabilize C in a hypervalent state, particularly when it is bonded with nonmetallic elements. Most of the work so far has focused on synthesizing organic molecules with a high coordination number of C. Our results provide a good measure of the resistivity of C toward forming hypervalent compounds with nonmetallic elements and of the barrier of reaction involving C-O bonds.