In this study, cobalt oxide (Co3O4)/graphene composites were synthesized through a simple chemical method at various calcination temperatures. We controlled the crystallinity, particle size and morphology of cobalt oxide on graphene materials by changing the annealing temperatures (200, 300, 400oC). The nanostructured Co3O4/graphene hybrid materials were studied to measure the electrochemical performance through cyclic voltammetry. The Co3O4/graphene sample obtained at 200oC showed the highest capacitance of 396 Fg-1 at 5 mVs-1. The morphological structures of composites were also examined by scanning electron microscopy and transmission electron microscopy (TEM). Annealing Co3O4/graphene samples in air at different temperatures significantly changed the morphology of the composites. The flower-like cobalt oxides with higher crystallinity and larger particle size were generated on graphene according to the increase of calcination temperature. A TEM analysis of the composites at 200oC revealed that nanoscale Co3O4 (~7 nm) particles were deposited on the surface of the graphene. The improved electrochemical performance was attributed to a combination effect of graphene and pseudocapacitive effect of Co3O4.