Unmanned aerial vehicles (UAVs) have gained considerable interests in numerous civil applications. To push forward its potentials, cellular-connected UAVs have been introduced. Nevertheless, cellular networks face several bottlenecks such as spectrum scarcity and limited concurrent connectivity. To address these issues, non-orthogonal multiple access (NOMA) can be adopted. NOMA provides several opportunities for cellular-connected UAVs such as larger rate region, balanced performance between system throughput and fairness, and reduced delay. In this paper, we review important findings of the related studies, and outline new opportunities and challenges in NOMA for cellular-connected UAVs. Monte-Carlo simulations are then performed to analyze the new aerial user’s (AU)’s signal characteristics and evaluate the NOMA performance for co-existence of AU and terrestrial user (TU). Our preliminary results show that NOMA is a promising strategy for cellular-connected UAVs.