There is a growing interest in the use of untethered underwater vehicles. These vehicles require robust and error-free underwater communication for transmission of mission-critical data. In contrast, the requirements for sensor payloads are often less stringent. Depending on the type of data, different Quality-of-Service (QoS) demands can be identified. To maximize the bandwidth utilization of underwater communication links, a modulation that provides the possibility to have multiple QoS levels within a single transmission is introduced. This flexible modulation is labelled Multi-Stream Frequency-Repetition Spread Spectrum (MSFRSS) and provides configurable quality-of-service levels for distinct parts of the communicated message. Early channel replay simulations encourage future tests of MSFRSS in alternative configurations and environments.