Until very recently, it was generaly accepted that the Old Gods were on Azeroth as far back as the we look. They were considered to be an integral part of Azeroth itself, and therefore impossible to remove without destroying Azeroth.

This mostly seems to come from:

The Old Gods and the Ordering of Azeroth

Shadows & Light also discusses the Titans, but I believe the information they give is very limited. As they said themselves, very little is commonly known by scholars.

Returning to The Old Gods and the Ordering of Azeroth, we must ask ourselves, how trustworthy is it as a source of lore? Not very. It's a text found in a book placed in several places around Azeroth, and thus it is something most likely written by particularly knowlegeable scholars. The fact that it only mentions Earthen and Sea giants as the Titans creations, just goes to show how incomplete it is a source of knowledge.

In any case, the knowledge we had about the period of the Old Gods and the Titans is very limited. In WoW itself there are a few more interesting sources of data, namely Un'Goro and Uldaman, but the most important text to come from all of this is that related to the Lore Keeper of Norgannon. His information refers mostly to the Dwarves and Troggs and can be found here.

More recently, WotLK brought us a great wealth of new Data. Prime amongst these is the Tribunal of Ages. I will now analyse this text quote by quote:

• Brann Bronzebeard says: Take a moment and relish this with me! Soon all will be revealed! Okay then, let’s do this!
• Abedneum: Critical threat index. Void analysis diverted. Initiating sanitization protocol.
• Kadrak says : Security breach in progress. Analysis of historical archives transferred to lower priority queue. Countermeasures engaged.
• Marnak says: Threat index threshold exceeded. Celestial archive aborted. Security level heightened.
• Abedneum says: Warning! Life form pattern not recognized. Archival processing terminated. Continued interference will result in targeted response. Alert! Security fail safes deactivated. Beginning memory purge… System online. Life form pattern recognized. Welcome Branbronzan. Query?

This is just the introduction. All that we can take from here is that anything Abedneum, Kadrak and Marnak says comes directly from the Titan's own historical archives. If we must suspect any alteration, it would be caused by Loken, but considering the content, I have doubts that it is so.

• Brann Bronzebeard says: Query? What do you think I’m here for? Tea and biscuits? Spill the beans already! Tell me how that dwarfs came to be! And start at the beginning!

Brann wants to know where the Dwarves come from. Therefore we can expect this to fit in with the content of the Discs of Norgannon from Uldaman.

• Abedneum says: Accessing prehistoric data. Retrieved. In the beginning Earthen were created to-

In the begining: The Earthen were created. The logical choice to start with, if they are going to talk about Dwarves. Not much to really say.

• Brann Bronzebeard says: Right, right! I know that the Earthen were made of stone to shape the deep reaches of the world but what about the anomalies? Matrix non-stabilizing and whatnot.
• Abedneum says: Accessing. In the early stages of its development cycle Azeroth suffered infection by parasitic, necrophotic symbiotes.

We all knew that the Old Gods came in the early stages of Azeroth's development cycle. What we don't know is wether that cycle was tiggered by the Titans or not. This does, however, tell us something about the nature of the Old Gods. They are 'parasitic, necrophotic symbiotes'. 'Necrophotic' doesn't correspond to any real terms, but necro refers to death, and photic to light. It's hard to really know what it refers to. On the other hand, 'parasitic' and 'symbiote' do have a meaning that we can understand. We all know what 'parasitic' refers to: an external living agent that benefits from close association to another living being, while causing harm to this same host. We don't have to be scientific about the text to understand this. There are other words further down in the text that define the Old Gods as an external agent that 'infects' the 'host'. Some have argued that this may just be a missuse of the words in order to make the text sound scientific. However, the use of the word 'Symbiote' suggests that there is sufficient scientific knowledge behing the text to make the wording of this text much more trustworthy. And that is because Symbiot refers to Symbiosis, and parasitism is a form of symbiosis. The further usage of semi-apropriate terms merely corroborates my assertion that the Old Gods are external beings that came to Azeroth at some point. They were not at the time imperative to Azeroth's survival, and their origin is not inherently tied to Azeroth.

• Brann Bronzebeard says: Necro-what? Speak bloody common will ya?
• Abedneum says: Designation: Old Gods. Old Gods rendered all systems, including Earthen defenseless in order to facilitate assimilation. This matrix destabilization has been termed the Curse of Flesh. Effects of destabilization increased over time.
• Brann Bronzebeard says: Old Gods eh? So they zapped the Earthen with this Curse of Flesh. And then what?
• Kadrak says: Accessing. Creators arrived to extirpate symbiotic infection. Assessment revealed that Old God infestation had grown malignant. Excising parasites would result in loss of host.
• Brann Bronzebeard says: If they killed the Old Gods Azeroth would have been destroyed.

This is where the crux of my argument lies. To begin with, they tell us that in order to facilitate assimilation, the Old Gods placed the curse of flesh on various systems, including the Earthen. After Brann summarised thi point he asked: "And then what?" The answer can therefore be deduced to refer to a consequence: and that consequence is the arrival of the Titans to remove the Old Gods. That necessarily means that they were elsewhere at that point. This means that the Titans came to Azeroth not once, but twice. Once before, where they created the Earthen and the other systems, and once after, to remove the Old Gods and restore Azeroth. Finally, what Kadrak says is that the parasites had 'grown malignant'. Usually, the word malignant is used to refer to a cancer, something that is inherent part of the cancer patient. However, it can also be used to say that an ailment has reached a point where it will get worse and worse. In this case, it means that removing the parasite would kill the host. This the result of the "assimilation" mentioned. The only choice, of course, was to neutralise the Old Gods' powers and imprison them. I'll also point out the use of other words that point towards the Old Gods being external agents: "infection", "assimilate", "infestation" and "host".

• Kadrak says: Correct. Creators neutralized parasitic threat and contained it within the host. Forge of Wills and other systems were instituted to create new Earthen. Safeguards were implemented and protectors were appointed.

Pretty much says what I said. It also mentions the creation of new Earthen and the apointment of protectors (presumably the Ulduar Sentinels (Loken, Thorim, etc) and the Dragonflights. Maybe also several giant types. Possibly the Well of Eternity.).

• Brann Bronzebeard says: What protectors?
• Kadrak says: Designations: Aesir and Vanir or in common nomenclator Storm and Earth Giants. Sentinel Loken designated supreme. Dragon Aspects appointed to monitor evolution of Azeroth.

Like I said. Not sure if "Aesir and Vanir" refers to the Sentinels, the Giants or both. No mention of the Well, so it could be wrong.

• Brann Bronzebeard says: Aesir and Vanir. Okay. So the Forge of Wills started to make new Earthen. But what happened to the old ones?
• Marnak says: Additional background is relevant to your query. Following global combat between-
• Brann Bronzebeard says: Hold everything! The Aesir and Vanir went to war? Why?
• Marnak says: Unknown. Data suggests that impetus for global combat originated with prime designate Loken who neutralized all remaining Aesir and Vanir affecting termination of conflict. Prime designate Loken then initiated stasis of several seed races including Earthen, Giant and Vrykul at designated holding facilities.

It's hard to tell if this refers to the Aesir and Vanir going to war against an enemy, or aginst each other. The fact that Loken was the origin of the impetus for combat may mean that it is refering to the ogoing war between Iron and Stone. It explains why the Earthen went underground and why the Vrykul did as well, but not why a few remained above. It's hard to really know any details about this whole process, but one can speculate.

• Brann Bronzebeard: This Loken sounds like a nasty character. Glad we don’t have to worry about the likes of him anymore. So if I’m understanding you lads the original Earthen eventually woke up from this statis. And by that time this destabily-whatever had turned them into our brother dwarfs. Or at least dwarf ancestors. Hm?
• Marnak says: Essentially that is correct.
• Brann Bronzebeard says: Well now. That’s a lot to digest. I’m gonna need some time to take all of this in. Thank you!
• Abedneum says: Acknowledged Branbronzan. Session terminated. [1]

Conclusion.

Well, I hope I've managed to convince you that the Titans did come before the Old Gods.

One loophole remains open, though. It has been suggested that the Old Gods were already present, and that they only began to 'assimilate' Azeroth after the Titans left. I see no reason to believe this. Why didn't they assimilate it before? Why did the Titans not notice them? It's an unecessary complication. Someone mentioned that the Titans fought the Elementals before they fought the Old Gods, but I have no idea how they manage to conclude that from The Old Gods and the Ordering of Azeroth. It just isn't conclusive.