We report a simple and novel coordination compound precursor route to synthesize shape-controlled Co₃O₄ nanostructures. The resultant morphologies of the nanostructures can be tailored by controlling the reaction temperature and the sodium hydroxide concentrations during the growth process. Temperature was found to play an important role in the formation of CoOOH nanosheets and Co₃O₄ nanooctahedra. A too low temperature (<100 °C) is disadvantageous for the formation of regular hexagonal CoOOH nanosheets and a too high temperature (>200 °C) is unfavourable for the formation of Co₃O₄ nanooctahedra. At a certain temperature, sodium hydroxide concentration is also crucial for the formation of different shapes of Co₃O₄ nanostructures. A possible growth mechanism governing the formation of such nanostructures is discussed. The gas sensing properties of the as-synthesized nanostructures are investigated in detail, which reveals that the as-prepared Co₃O₄ nanostructures exhibit superior sensitivity to CO and CH₄ relative to bulk Co₃O₄ at room temperature, as well as good reproducibility and short response/recovery times. The as-prepared Co₃O₄ nanostructures could have potential applications in nanosensors.