Recently, graphene-based nanomaterials, in the form of two dimensional substrates or three dimensional foams, have attracted considerable attention as bioactive scaffolds to promote the differentiation of various stem cells towards specific lineages. On the other hand, the potential advantages of using graphene-based hybrid composites directly as factors inducing cellular differentiation as well as tissue regeneration are unclear. This study examined whether nanocomposites of reduced graphene oxide (rGO) and hydroxyapatite (HAp) (rGO/HAp NCs) could enhance the osteogenesis of MC3T3-E1 preosteoblasts and promote new bone formation. When combined with HAp, rGO synergistically promoted the spontaneous osteodifferentiation of MC3T3-E1 cells without hindering their proliferation. This enhanced osteogenesis was corroborated from determination of alkaline phosphatase activity as early stage markers of osteodifferentiation and mineralization of calcium and phosphate as late stage markers. Immunoblot analysis showed that rGO/HAp NCs increase the expression levels of osteopontin and osteocalcin significantly. Furthermore, rGO/HAp grafts were found to significantly enhance new bone formation in full-thickness calvarial defects without inflammatory responses. These results suggest that rGO/HAp NCs can be exploited to craft a range of strategies for the development of novel dental and orthopedic bone grafts to accelerate bone regeneration because these graphene-based composite materials have potentials to stimulate osteogenesis.