For the sake of making things much, much simpler, most worlds I'm familiar with have a defining feature of language: there is a common language. This allows for universal communication and overcomes what would otherwise be time-limiting obstacles for one species (or race) to communicate with another.
However - my question here revolves around the fact that we can't always be so lucky. What if there was no universal language? What if the biology of the two species was different enough that they had defining phonetic differences (which, I think, should be the more likely scenario whenever there are two intelligent species coming into contact with one another). Imagine if you were to introduce to a human species an intelligent species with all the defining characteristics of the human phonetic biology (esophagus of relative length, vocal chords, lips, teeth, shape of mouth) but they were missing a tongue. The time to develop a universal language would take time - and that's given that humans with tongues can talk like humans without tongues.
I'm looking for the best example of how this might have occurred historically (among new civilizations meeting and who had no idea how to translate each other's language) or fantasy-historically (a permanent language-replacement which shows the best example of massively reducing the time taken for written translations). I am not looking for any example of a "Universal Translator" type answers, as that answer is the equivalent of everyone being able to inherently speak the same language, unless it's a well established methodology which has been taken into serious consideration.