A new phenomenon of structural reorganization is discovered and characterized for a gold-carbon system by in-situ atomic-resolution imaging at temperatures up to 1300 K. Here, a graphene sheet serves in three ways, as a quasi transparent substrate for aberration-corrected high-resolution transmission electron microscopy, as an in-situ heater, and as carbon supplier. The sheet has been decorated with gold nanoislands beforehand. During electron irradiation at 80 kV and at elevated temperatures, the accumulation of gold atoms has been observed on defective graphene sites or edges as well as at the facets of gold nanocrystals. Both resulted in clustering, forming unusual crystalline structures. Their lattice parameters and surface termination differ significantly from standard gold nanocrystals. The experimental data, supported by electron energy loss spectroscopy and density-functional theory calculations, suggests that isolated gold and carbon atoms form - under conditions of heat and electron irradiation - a novel type of compound crystal, Au-C in zincblende structure. The novel material is metastable, but surprisingly robust, even under annealing condition.