Marvel wikia retcons its first appearance as xmen#101, but phoenix force isn't in this issue, phoenix is. At some point between its publication and now the story must've changed to involve a cosmic god, but I wonder if before then phoenix's origin was intended to be an extreme version of fantastic 4's origin beyond just an homage.
I just started reading xmen#125 and once again in a flashback this is how the event is described:
Her body was consumed by the intense radiation. But her mind refused to die. Driven by her love for Scott Summers, she achieved her full potential as a psi --becoming, briefly, an entity of pure thought-- before finally reforming as Phoenix.
So when does phenix force actually bocme a thing? Were there any other out of universe (as I'll reach the in universe ones eventually) explanations of the phoenix's power before then? Shouldn't the wiki at least mention if a part of an article is a retcon?
Edit: I think it appears first in xmen 153, where Kitty pryde tells colossus's sister a bedtime story loosely based on the xmen. In the story Jean's soul manages to defeat Phoenix.
As with any good comics story, it's complicated. :)
Jean crashes into the bay and energes as Phoenix in X-Men #101
The cosmic threat of Phoenix is explored up until X-Men #108.
Then you have Dark Phoenix from #129 to #138.
But the idea of Jean and Phoenix as separate entities was a retcon from much, much later, starting in Avengers #263 when a strange pod is discovered at the bottom of the bay, which is then opened in Fantastic Four #286.
Beyond the excellent answer already given, I'll add a silly comics-are-weird, chronological answer:
We do see an appearance by the Phoenix (or something likey destined to give birth to the Phoenix) in around 100,000 BC - meeting with the cave-person version of the Avengers.
For anyone who hasn't read the cave-person avengers, I'll just say: