Growth of nanocrystalline single- and bi-layer graphene on sapphire (0001) substrates is achieved by van der Waals molecular beam epitaxy (MBE) with a solid carbon source. Gradients in substrate temperature and incident carbon flux enable the exploration of growth parameters for fabrication of graphene layers. Raman spectroscopy reveals that fabrication of single layer, bilayer or multilayer graphene crucially depends on MBE growth conditions. Atomic force microscopy (AFM) images uncover the presence of etch pits in layers grown at higher substrate temperatures (around 1200 °C). The average spacing between etch pits (of about 100 nm) defines an upper limit of the nanocrystal size. Sharp Raman bands in the grown single-layer graphene nanocrystals indicate high crystallinity. Formation of etch pits during growth is regarded as evidence for a removal mechanism of carbon by reduction of sapphire. Growth of graphene on sapphire by MBE is driven by the interplay between carbon deposition and its removal. Tuning the easily controlled incident carbon flux and the markedly temperature dependent carbo-thermal reduction of sapphire should enable the growth of high quality graphene layers on large area sapphire substrates. © 2014 Elsevier Ltd. ; Work supported by ONR (N000140610138 and Graphene MURI), AFOSR (FA9550-11-1-0010), EFRC Center for Re-Defining Photovoltaic Efficiency through Molecule Scale Control (award DE-SC0001085), NSF (CHE-0641523), NYSTAR, CSIC-PIF (200950I154), Spanish CAM (Q&C Light (S2009ESP-1503), Numancia 2 (S2009/ENE-1477)) and Spanish MINECO (AIC-B-2011-0806, TEC2011-29120-C05-04, MAT2011-26534). ; S2009/ESP-1503/Q&CLight ; S2009/ENE-1477/Numancia2 ; Peer Reviewed