Abstract Driven by the need to ensure the connectivity of an unprecedentedly huge number of IoT devices with no human intervention the issues of massive connectivity have recently become one of the main research areas in IoT studies. Conventional wireless communication technologies are designed for Human-to-Human (H2H) communication which leads to major problems in primary access, channel utilization and spectrum efficiency when massive numbers of devices require connectivity. Current random access procedures are based on a four-step handshaking with control messages which contradicts the requirements of IoT applications in terms of small data payloads and low complexity. Targeted channel utilization and spectrum efficiency cannot be achieved using traditional orthogonal approaches. Thus the goal of our work is to review the most recent developments and critically evaluate the existing work related to the evolution of network access methods in the new communication era. The paper covers three major aspects: first the primary random access procedures, proposed for IoT communications are discussed. The second aspect focuses on the approaches for integration of existing random multiple access schemes with non-orthogonal multiple access methods (NOMA). This integration of random access procedures with NOMA opens a new research trend in the field of massive connectivity. Operating on space domains additional to the physical domain such as code and power domains, NOMA integration targets increased channel utilization and spectrum efficiency to complement the flexibility of random access. On the other hand, the design of efficient algorithms for massive connectivity in IoT is also challenged by the highly application and environmentally dependent traffic model. A new angle of tackling this problem has emerged thanks to the extensive developments in machine learning and the possibilities of their incorporation in communication networks. Thus, the final aspect this review paper addresses are the newly emerging research directions of incorporating machine learning (ML) methods for providing efficient IoT connectivity. Breakthrough ML techniques allow wireless networking devices to perform transmissions by learning and building knowledge about the communication and networking environment. A critical evaluation of the large body of work accumulated in this area in the most recent years and outlining of some major open research issues concludes the paper.