Flying in dynamic, urban, highly-populated environments represents an open problem in robotics. State-of-the-art (SoA) autonomous Unmanned Aerial Vehicles (UAVs) employ advanced computer vision techniques based on computationally expensive algorithms, such as Simultaneous Localization and Mapping (SLAM) or Convolutional Neural Networks (CNNs) to navigate in such environments. In the Internet-of-Things (IoT) era, nano-size UAVs capable of autonomous navigation would be extremely desirable as self-aware mobile IoT nodes. However, autonomous flight is considered unaffordable in the context of nano-scale UAVs, where the ultra-constrained power envelopes of tiny rotor-crafts limit the on-board computational capabilities to low-power microcontrollers. In this work, we present the first vertically integrated system for fully autonomous deep neural network-based navigation on nano-size UAVs. Our system is based on GAP8, a novel parallel ultra-low-power computing platform, and deployed on a 27 g commercial, opensource CrazyFlie 2.0 nano-quadrotor. We discuss a methodology and software mapping tools that enable the SoA CNN presented in [1] to be fully executed on-board within a strict 12 fps realtime constraint with no compromise in terms of flight results, while all processing is done with only 94 mW on average - 1% of the power envelope of the deployed nano-aircraft.