Cobalt-based catalysts undergo a massive and spontaneous reconstruction to form uniform triangular nanoislands under Fischer-Tropsch (FT) conditions. This reconstruction is driven by the unusual and synergistic adsorption of square-planar carbon and CO at the 4-fold edge sites of the nanoislands, driving the formation of triangular islands. The size of the nanoislands is determined by the balance between energy gain from creating C/CO-covered edges and energy penalty to create C/CO-covered corners. For carbon chemical potentials corresponding to FT conditions, triangular Co islands with 45 Co atoms (about 2 nm) are the most stable surface structure. Decreasing the carbon chemical potential and hence the stability of square-planar carbon favors the formation of larger islands, until reconstruction becomes unfavorable and CO-covered terraces are thermodynamically the most stable. The predicted structure of the islands is consistent with in situ scanning tunneling microscopy images obtained for the first time under realistic FT reaction conditions on a Co(0001) surface.