Gold Nano-cages are synthesized via a galvanic replacement reaction between as-prepared silver nanocubes and Au3+ (HAuCl4) ions. Graphene nano-sheets are synthesized using a chemical procedure and are used as support to immobilize the gold nano-cages. The morphology, surface properties, and composition of the prepared nano-composites are studied using scanning electron microscopy, Bruanauer-Emmett- Teller surface area analysis, and energy dispersion X-ray spectroscopy techniques, respectively. Electrocatalytic activity of the prepared nano-structure toward sodium borohydride oxidation is studied. Gold nano-cages on graphene support show a better electrocatalytic activity than bulk Au electrode.