Techniques for random access (RA) in a cellular internet-of-things (CIOT) are discussed. An example apparatus configured to be employed within a User Equipment (UE), comprises a receiver circuitry, a processor, and transmitter circuitry. The receiver circuitry is configured to receive RA resource allocation information via one of a system information message or a downlink control information (DCI) message. The processor is operably coupled to the receiver circuitry and configured to: select a RA preamble sequence; generate a payload; and spread the payload via a spreading sequence. The transmitter circuitry is configured to transmit, based on the RA resource allocation information, a RA message comprising the RA preamble sequence and the payload, wherein the RA message is transmitted in a RA slot. The receiver circuitry is further configured to receive a response comprising a device identity of the UE and one of an uplink (UL) grant or a RA reject message.