The structural, electronic and magnetic properties of the neutral and cationic cobalt oxide clusters (CoO)qn (n=3−10, q=0,+1) have been studied using a modified basin-hopping Monte Carlo (BHMC) algorithm refined by spin-polarized DFT. A systematic search of global minimum structures predicts new global minima of (CoO)0∕+9 and reproduced other minima that are in excellent agreement with previous works. For most low-spin and high-spin states, the structural transition from planar-like to compact structure occurs at (CoO)0∕+5, which is in contrast with the general notion that the structural changes at (CoO)0∕+6. Supported by the results of the binding energy, second-order total energy difference, chemical hardness, chemical potential and HOMO-LUMO gap confirms the stability of (CoO)4. Results of the spin magnetic moments for the global minima show that (CoO)4 and (CoO)8 spin configurations exhibit a fully antiferromagnetic (AFM) ordering, while (CoO)9 spin displays the highest ferromagnetic (FM) ordering. Interestingly, elongation of Co–Co bond in (CoO)4 causes O being polarized by the neighboring Co atoms that accordingly follows the Goodenough-Kanamori-Anderson rule of FM super-exchange coupling for the Co-O-Co structural rearrangement to 90∘ (D4h structure) in order to accommodate the spin magnetic ordering changes. This rearrangement is a result of the valence band being shifted away from the Fermi level to lower energy causing high population of the spin-up density of state and leading to the asymmetrical polarization of the whole (CoO)4 structure. As far as the dissociation energy surfaces are concerned, the first ever such surfaces are constructed corresponding to (CoO)qn→(CoO)qm+(CoO)(n−m), which identify a complete dissociation pathway linking the cationic and neutral clusters and finally confirm (CoO)0∕+4 as the most stable cluster compared to the rest.