Buoyancy driven granular convection is studied for a shallow, vertically shaken granular bed in a quasi 2D container. Starting from the granular Leidenfrost state, in which a dense particle cluster floats on top of a dilute gaseous layer of fast particles (Meerson et al. in Phys Rev Lett 91:024301, 2003; Eshuis et al. in Phys Rev Lett 95:258001, 2005), we witness the emergence of counter-rotating convection rolls when the shaking strength is increased above a critical level. This resembles the classical onset of convection—at a critical value of the Rayleigh number—in a fluid heated from below. The same transition, even quantitatively, is seen in molecular dynamics simulations, and explained by a hydrodynamic-like model in which the granular material is treated as a continuum. The critical shaking strength for the onset of granular convection is accurately reproduced by a linear stability analysis of the model. The results from experiment, simulation, and theory are in good agreement. The present paper extends and completes our earlier analysis (Eshuis et al. in Phys Rev Lett 104:038001, 2010).