Abstract Existing algorithms for improving speech intelligibility in a noisy environment generally focus on modifying the acoustic features of live, recorded or synthesized speech while preserving the phonetic composition (the message). In this paper, we present an algorithm for text-to-speech systems that operates at a higher level of abstraction, the message-level. We use a paraphrasing system to adjust the linguistic content of the intended message such that the speech intelligibility improves under noisy conditions. To distinguish the intelligibility among paraphrases, we use the numerical integration of a normalized log-likelihood function over different signal-to-noise conditions. Objective evaluation results show that the developed measure is able to distinguish the intelligibility among paraphrases. Results from subjective evaluation confirm the effectiveness of our objective measure.