According to Fantastic Beasts and Where To Find Them, the phoenix lives an inordinately long life, but it is not immortal:
The phoenix lives to an immense age as it can regenerate, bursting into flames when its
body begins to fall and rising again from the ashes as a chick.
Fantastic Beasts and Where to Find Them - page 32 - Scholastic - An A-Z of Fantastic Beasts
All the circumstances under which a Harry Potter Phoenix will regenerate or not be killed is not known. However, in Order of the Phoenix Fawkes swallows the Avada Kedavra curse as he's protecting Dumbledore from Voldemort, and he does survive that. It's entirely possible that, so ostensibly it should be possible for him to survive the Basilisk's gaze as well. But I think, from what we do know about phoenixes in Harry Potter, that something would have to happen -- like the Basilisk's stare would have to kill Fawkes and Fawkes would have to regenerate.
Personally, because Fawkes is never a Phoenix chick in the Chamber of Secrets, even after encountering the Basilisk, I think he never directly made eye contact with the Basilisk and, therefore, was never at risk for death and regeneration.