Cellular Internet of Things (C-IoT) is one of the emerging 5G technologies. 4G LTE being the most promising cellular technology so far and is a suitor for serving C-IoT devices. In future millions of C-IoT devices will be deployed in the coverage of a single 4G LTE base station. However, the existing random access (RACH) mechanism in 4G LTE is not designed to connect millions of devices. Hence, in this paper, we propose a novel RACH mechanism that allows millions of C-IoT devices to associate with the base station within the existing 4G LTE framework. 3GPP has proposed an extended access barring mechanism to solve this problem for machine type communication (MTC). We compare the performance of the proposed RACH mechanism with the existing 3GPP extended access barring mechanism through analysis. Further, through simulation results, we show that the proposed mechanism is faster and saves power when compared to existing 3GPP extended access barring mechanism under perfect synchronization. © 2016 IEEE.