Efficiency of cellular-connected UAVs is challenged by spectrum inefficiency, limited number of concurrent connectivity, and strong interference. To overcome these issues, in this paper, we study the performance of downlink non-orthogonal multiple access for cellular-connected UAVs. We develop a novel framework based on stochastic geometry for the co-existence of aerial users (AUs) and terrestrial users (TUs), where the spatial distribution of the base stations (BSs) follows a Poisson Point Process. In our analysis, two user association policies and two types of receive antennas are considered while an inter-cell interference coordination (ICIC) technique is also in place. As the main performance measures, we then analytically derive the coverage probability and average rate of AUs and TUs. These derivations are then used to provide quantitative insights on the impact of different system parameters and settings including AU’s altitude, TU’s distance from the BS, power allocation, successive interference cancellation (SIC) constraints, user association policy, antenna beamwidth, and the number of coordinated BSs. Based on our analysis we then propose an interference-aware scheme based on maximum-SINR user association, directional antenna, and ICIC. A benchmark scheme based on minimum-distance user association, omni-directional antenna, and without ICIC is considered. Compared to the benchmark scheme, our proposed scheme improves the AU’s coverage probability by threefold and TU’s average rate by six-fold. Compared to the orthogonal multiple access, our proposed scheme trades off a slight reduction in the AU’s coverage probability (~1%) with a significant increase in the achieved rate of the TUs (603Kbps/resource block).