In this letter, we propose a message-embedded random access (MERA) scheme to simultaneously transmit both preambles (PAs) and messages (MSGs) as MSG-embedded PAs based on auto-and cross-correlation properties of Zadoff-Chu sequences using distinct root numbers. The proposed MERA scheme enables machine nodes to transmit small-sized data during a PA transmission on control channel (i.e., PRACH) without using any scheduling mechanism and resources on data channel (i.e., PUSCH). The performance of the proposed MERA scheme is mathematically analyzed and evaluated through simulations in terms of PA detection probability, MSG decoding probability, and the throughput of MSG transmissions on PRACH.