Source EditThel'zan's Phylactery appears after killing Icestorm in the Dragonblight. [63, 27]
As a quest objective Edit
While on the Changing Icestorm, talk to "Wyrmbait", tell him to get Icestorm, wait for the harpoons to catch her and unload from range. Once she dies, the phylactery will drop on the ground for all to loot.