In Cellular Internet-of-Things, random access channel (RACH) mechanism is used by machine-to-machine communication (M2M) devices to connect to a base station (BS) for any information exchange. However, increase in the number of M2M devices increases the network contention and reduces the number of RACH successes. In order to address this problem, we propose a successive interference cancellation based non-orthogonal random access (SIC-NORA) mechanism. In the proposed mechanism, each M2M device is allowed to repeat its transmission in a finite number of time slots within a radio frame. The messages of two devices that collide in the same slot can be decoded if the difference in the arrival time of their messages is greater than the predetermined threshold. Upon the successful RACH from an M2M device, the BS applies SIC in the current and all previous slots of the radio frame to decode messages of other devices for enhanced RACH success. A Markov chain model of the proposed mechanism is developed and the corresponding steady-state probabilities are derived. Through extensive numerical results, we show that the proposed mechanism performs better than state-of-the-art RACH mechanisms in terms of number of RACH successes and average access delay. Further, the proposed mechanism improves the success rate by 65.3% and 30.3% as compared to NORA and SIC-based RACH mechanism, respectively. Moreover, there is 29.6% and 15% reduction in the number of time slots required for 2times 10{5} devices to get success with the proposed mechanism as compared to NORA and SIC-based RACH mechanism, respectively, at the corresponding optimal value of radio frame length. © 2013 IEEE.