In a multi-user cluster of the downlink non-orthogonal multiple access (NOMA) system, in order to satisfy the service requirements of different users, the power allocation algorithm with quality of service (QoS) guarantee and max-min fairness criterion is proposed. According to different user requirements, an optimization problem is formulated which is aiming for the max-min fairness criterion under the total power and minimum rate requirement constraints. The problem is solved by the bisection method and Karush-Kuhn-Tucker (KKT) conditions. Simulation results show that the power allocation algorithm guarantees users’ QoS requirements and satisfies the fairness criterion. Compared with the traditional multi-access system, the throughput of the NOMA system is greatly improved.