In the context of massive Machine Type Communications (mMTC), the Narrowband Internet of Things (NB-IoT) technology is envisioned to efficiently and reliably deal with massive device connectivity. Hence, it relies on a tailored Random Access (RA) procedure, for which theoretical and empirical analyses are needed for a better understanding and further improvements. This paper presents the first data-driven analysis of NB-IoT RA, exploiting a large scale measurement campaign. We show how the RA procedure and performance are affected by network deployment, radio coverage, and operators’ configurations, thus complementing simulation-based investigations, mostly focused on massive connectivity aspects. Comparison with the performance requirements reveals the need for procedure enhancements. Hence, we propose a Machine Learning (ML) approach, and show that RA outcomes are predictable with good accuracy by observing radio conditions. We embed the outcome prediction in a RA enhanced scheme, and show that optimized configurations enable a power consumption reduction of at least 50%. We also make our dataset available for further exploration, toward the discovery of new insights and research perspectives.