Graphene and its analogues have some of the highest predicted melting points of any materials. Previous work estimated the melting temperature for freestanding graphene to be a remarkable 4510 K. However, this work relied on theoretical methods that do not accurately account for the role of bond breaking or complex bonding configurations in the melting process. Furthermore, experiments to verify these high melting points have been challenging. Practical applications of graphene and carbon nanotubes at high temperatures will require a detailed understanding of the behavior of these materials under these conditions. Therefore, we have used reliable ab initio molecular dynamics calculations to study the initial stages of melting of freestanding graphene monolayers between 4000 and 6000 K. To accommodate large defects, and for improved accuracy, we used a large 10 × 10 periodic unit cell. We find that the system can be heated up to 4500 K for 18 ps without melting, and 3-rings and short lived broken bonds (10-rings) are observed. At 4500 K, the system appears to be in a quasi-2D liquid state. At 5000 K, the system is starting to melt. During the 20 ps simulation, diffusion events are observed, leading to the creation of a 5775 defect. We calculate accurate excitation energies for these configurations, and the pair correlation function is presented. The modified Lindemann criterion was calculated. Graphene and nanotubes together with other proposed high melting point materials would be interesting candidates for experimental tests of melting in the weightless environment of space.