Nanostructured cobalt oxide (Co3O4) electrodes were prepared by two different methods. The first one involved the synthesis of Co3O4 nanoparticles through a nanocasting route using commercial silica gel as a sacrificial template, and in the second one, the Co3O4 electrodes were prepared by thermal decomposition. The electrodes were characterized by different techniques, such as scanning electron microscopy, energy-dispersive X-ray analysis (EDX), X-ray diffraction (XRD), transmission electron microscopy, X-ray photoelectron spectroscopy (XPS), and cyclic voltammetry. EDX, XRD, and XPS show a characteristic spinel-type structure and a similar chemical composition for the two nanostructured cobalt oxides. However, the surface morphology is different. The electrochemical oxidation of cyanide and phenol in alkaline medium were used as test reactions. The electrocatalytic activity of the nanocrystalline Co3O4 electrodes for cyanide and phenol oxidation turned out to be highly dependent on the electrode preparation method. ; Financial support by the Generalitat Valenciana grant no. GV05/136, no. GV06/106, and no. RED ARVIV/2007/076) and Ministerio de Educación y Ciencia (MAT2007-60621 and MAT2005-00262) projects.