Regardless of its successful clinical applications, load-bearing implant applications of hydroxyapatite (HA) remain problematic due to its intrinsic property limitations. Recent findings of the promising biocompatibility of graphene imply the possibilities of it being potentially used as additives for HA-based composites with enhanced mechanical properties. Here we report HA-reduced graphite oxide nanocomposites synthesized by a liquid precipitation approach followed by spark plasma sintering consolidation. The reduced graphite oxide (rGO) consisted of 2-6 layers of graphene. Rod-like HA grains with the dimensions of ∼9 nm in diameter and 20-45 nm in length exhibited oriented nucleation and epitaxial growth on graphene flakes. The (300) plane of HA crystals formed a coherent interfacial bond with the graphene wall and the section of the graphene sheet built a strong interface with the (002) plane of HA crystals. These structural features gave rise to enhanced densification and precluded grain growth of HA in the spark plasma sintered pellets. Fracture toughness of the HA-rGO composites reached 3.94 MPa m1/2, showing a 203% increase compared to pure HA. Crack deflection, crack tip shielding and crack bridging at the HA-rGO interfaces were disclosed as the major strengthening regimes in the composites. The enhanced mechanical properties together with the improved proliferation and ALP activity of the human osteoblast cells suggest a great potential of the composites for biomedical applications.