His real battle as a follower of the Lord of Light was to fight the Lord of Dark and his followers (others). Melisandre explicitly makes it clear at the end of the last season (S03E10) that he needs to go North to fight the growing power there.
More than Melisandre it is Ser Davos who urged Stannis to go North. The Nights Watch sent letters to all the claimants of the Iron Throne, and Davos thinks that only a true king will heed their call and protect the Seven Kingdoms. Melisandre's revelation only comes later, though it very much confirms where Stannis would be heading.