This paper investigates the coexistence between two key enabling technologies for fifth generation (5G) mobile networks, non-orthogonal multiple access (NOMA), and millimeter-wave (mmWave) communications. Particularly, the application of random beamforming to mmWave-NOMA systems is considered in order to avoid the requirement that the base station know all the users’ channel state information. Stochastic geometry is used to characterize the performance of the proposed mmWave-NOMA transmission scheme by using key features of mmWave systems, i.e., that mmWave transmission is highly directional and potential blockages will thin the user distribution. Two random beamforming approaches that can further reduce the system overhead are also proposed, and their performance is studied analytically in terms of sum rates and outage probabilities. Simulation results are also provided to demonstrate the performance of the proposed schemes and verify the accuracy of the developed analytical results.