Abstract: This paper considers a challenging communication scenario, in which users have heterogenous mobility profiles, e.g., some users are moving at high speeds and some users are static. A new non-orthogonal multiple-access (NOMA) transmission protocol that incorporates orthogonal time frequency space (OTFS) modulation is proposed. Thereby, users with different mobility profiles are grouped together for the implementation of NOMA. The proposed OTFS-NOMA protocol is shown to be applicable to both uplink and downlink transmission, where sophisticated transmit and receive strategies are developed to remove inter-symbol interference and harvest both multi-path and multi-user diversity. Analytical results demonstrate that both the high-mobility and low-mobility users benefit from the application of OTFS-NOMA. In particular, the use of NOMA allows the spreading of the high-mobility users' signals over a large amount of time-frequency resources, which enhances the OTFS resolution and improves the detection reliability. In addition, OTFS-NOMA ensures that low-mobility users have access to bandwidth resources which in conventional OTFS-orthogonal multiple access (OTFS-NOMA) would be solely occupied by the high-mobility users. Thus, OTFS-NOMA improves the spectral efficiency and reduces latency.