We introduce a Gaussian approximation potential (GAP) for atomistic simulations of liquid and amorphous elemental carbon. Based on a machine learning representation of the density-functional theory (DFT) potential-energy surface, such interatomic potentials enable materials simulations with close-to DFT accuracy but at much lower computational cost. We first determine the maximum accuracy that any finite-range potential can achieve in carbon structures; then, using a hierarchical set of two-, three-, and many-body structural descriptors, we construct a GAP model that can indeed reach the target accuracy. The potential yields accurate energetic and structural properties over a wide range of densities; it also correctly captures the structure of the liquid phases, at variance with a state-of-the-art empirical potential. Exemplary applications of the GAP model to surfaces of “diamondlike” tetrahedral amorphous carbon ($\textit{ta}$-C) are presented, including an estimate of the amorphous material’s surface energy and simulations of high-temperature surface reconstructions (“graphitization”). The presented interatomic potential appears to be promising for realistic and accurate simulations of nanoscale amorphous carbon structures.