We introduce a random access procedure where control and data information is transmitted in the same “access” slot. The key idea is data-overlayed control signalling together with a dedicated frequency area for compressive measurements exploiting sparse channel profiles and, potentially, sparse user activity. This architecture is resource-efficent since otherwise pilots have to be suitably placed in the time-frequency grid for every potential user. We analyze the achievable rates depending on the key design parameters and show by simulations that sparse signal processing algorithms are indeed “strong” enough to retrieve the information symbols out of the induced noise. Moreover, for the very high dimensional receive space applied in this paper, the number of detected users is only limited by the sheer complexity rather than performance.