Melisandre came from Asshai to serve Lord Stannis. We were told that she did it because she believed he was the Azor Ahai who'd save humanity by slaying the encroaching darkness. She even forged (a fake) Lightbringer for him, the heroes' sword which presumably the last Azor Ahai used to bring down the hands behind the last Long Night.
She then met Arya Stark in Riverlands and foretold that Arya would close many eyes; brown eyes, green eyes, blue eyes.
In S08E03 she meets Arya again and says the same words.
Arya at once realises that she means that Arya had to close the Night King's blue eyes and at once set out to do that.
Melisandre also hinted:
That Beric's only purpose for which the Lord of Light brought him back was protecting Arya during the battle so that she could kill the Night King.
So the question is, if she saw that:
Arya would be the one to kill Night King and is therefore the Azor Ahai she was looking for.
Why did she follow Stannis at all? There is no indication that she ever doubted that Stannis was manifestation of Azor Ahai until his last breath.