Co-B-based materials are widely used as catalysts for hydrogen generation through sodium borohydride self-decomposition. In the mid 1990s, the aqueous and organic chemistry involved in Co-B synthesis and handling was studied. Nevertheless, the exact microstructure of these catalysts has remained unsolved. Herein we present an exhaustive study which shows a new and complete microstructural view of a Co-B-based material together with the chemistry of the cobalt and boron involved. By using nanoscale-resolution microscopy and spectroscopy techniques, we have elucidated the role of boron compounds as stabilizers in a complex microstructure, which also explains its high catalytic performance and long-term stability. The catalyst is proposed to be made up of 1-3nm hcp Co0 nanoparticles embedded in amorphous CoxB (x=1, 2, 3), CoxOy, Co(BO2)2, and B2O3 phases alternatively or all together. All of these amorphous phases protect the nanocrystalline metallic core from growth and oxidation.