The rolling up of a graphene sheet into a tube is a standard visualization tool for illustrating carbon nanotube (CNT) formation. However, the actual processes of rolling up graphene sheets into CNTs in laboratory syntheses have never been demonstrated. Here we report conformal growth of graphene by carbon self-assembly on single-wall and multi-wall CNTs using chemical vapor deposition (CVD) of methane without the presence of metal catalysts. The new graphene layers roll up into seamless coaxial cylinders encapsulating the existing CNTs, but their adhesion to the primary CNTs is weak due to the existence of lattice misorientation. Our study shows that graphene nucleation and growth by self-assembly of carbon on the inactive carbon basal plane of CNTs occurs by a new mechanism that is markedly different from epitaxial growth on metal surfaces, opening up the possibility of graphene growth on many other non-metal substrates by simple methane CVD.