Unlike some other mythical creatures found in fantasy books, there is reference to the phoenix in ancient Jewish sources as far back as the Book of Job. When Job reminisces about his “good old days,” he says, “And I said, ‘I will perish with my nest, and like a chol [ וְכַחוֹל] I will multiply my days.’”1 According to many translations, the word chol refers to the phoenix.The reference is Job 29:18. I would make a distinction here. The word clearly means "phoenix" in rabbinic texts, but we shouldn't retroject that meaning into the much earlier reference in the Book of Job. The Revised Standard Version (cf. the NIV) translates the word as "sand," which indeed is one of its meanings and which fits the context.
[...]
Be that as it may, the Talmud and a midrash do take the meaning to be "phoenix" and they run with it. Follow the link for details.