Here, we report for the first time the synthesis of a 3-D self-assembled single crystalline platinum nanostructure directly on the graphene surface (PtNAGE) without using any harmful structural directing agents. A slow reduction method is used to prepare the desired platinum morphology. Initial formation of platinum nanoparticles and their homogenous dispersion on the surface of graphene have been observed 10 h after the commencement of the reduction using formic acid as the reducing agent. From these initially deposited seed particles, the growth starts on the {111} facets along the < 111 > direction and the nanostructure formation is completed within 72 h of the commencement of the reaction. The individual assembly has a diameter of similar to 80 nm. PtNAGE shows superior electrocatalytic activity towards oxygen reduction compared to graphene supported platinum (PtGE) and commercial carbon supported platinum (PtC) catalysts. PtNAGE is less vulnerable to strong hydroxyl adsorption compared to PtC and PtGE. Specific activity and mass activity of the catalyst are high compared to PtC by a factor of 6.50 and 1.80, respectively, and 4.00 and 3.05, respectively, compared to PtGE. The limiting current density of PtNAGE is 1.28 and 1.20 times higher than PtGE and PtC, respectively. Kinetic analysis of PtNAGE shows that the oxygen reduction reaction follows first order kinetics involving a four electron transfer mechanism with the direct formation of water. In addition to this, it has been observed that PtNAGE also prevents surface area degradation better than the commercial platinised carbon under potential induced conditions.