The dissociation of CO, a crucial step in the cobalt-catalyzed Fischer-Tropsch synthesis, was investigated by in situ scanning tunneling microscopy on Co(0001) at CO pressures up to 0.25 mbar and temperatures up to 493 K. A new type of surface reconstruction was observed that is formed by carbidic carbon, as shown by X-ray photoelectron spectroscopy. Using (CO)-C-13 and titrating C-13 with O-2, the surface carbon is shown to originate from CO. The results are in contrast to predictions by theoretical work. However, the dissociation rates are 3 orders of magnitude lower than the previously measured methanation rates under equivalent conditions.