Underground, as far as we know!
Back in 1.0, there was a place in Mor Dhona called the Crypt of Xandes (who I think was an Allagan king back in the day.) Here's a picture of it:
I...think this was the most concentrated place of crystal in 1.0's Mor Dhona, and after the Calamity, the impact and the imbalance of aether made a lot of the crystals in Mor Dhona go crazy (as you can see with the huge bunches of overaspected crystals, especially at Old Revenant's Toll), and I think this is what triggered the Tower to appear from the Crypt.
don't quote me on this, but i do know the general theory was that the Crypt was going to turn into the Crystal Tower.