The study of random surfaces, especially in the asymptotics of large genus, has been of increasing interest in recent years. Many geometrical questions have analogous formulations in the theory of random graphs with a large number of vertices, and results obtained in one area can inspire the other. In this paper, we are interested in the diameter of random surfaces, a basic measure of the connectivity of the surface. We introduce a new class of models of random surfaces built from random graphs and we compute the asymptotics of the diameter of these surfaces, which is logarithmic in the genus of the surface. The strategy of the proof relies on a detailed study of an exploration process which is the analogue of the breadth-first search exploration of a random graph. Its analysis is based on subadditive and concentration techniques.