We report the complete genome sequence of Carnobacterium gilichinskyi strain WN1359, previously isolated from Siberian permafrost and capable of growth under cold (0°C), anoxic, CO2-dominated, low-pressure (0.7-kPa) conditions in a simulation of the Mars atmosphere.