in Avatar: The Legend of Korra - Book 2: Spirits Episodes 7 and 8 (Beginnings Part 1 and 2) detail the story of the first Avatar Wan. in his time humans lived cities which were on the Lion Turtles who would gift people the power of the elements (what is currently known as Bending) when they venture into the Spirit Wilds.
the Lion Turtle that Wan's home was on gifted people the power of Fire and after Wan was banished for stealing the power of fire Wan was allowed to keep it, becoming the first Fire Bender to keep his power (as people would return the power of the elements when they returned).
after allowing the Spirit of Darkness, Vaatu, to separate from the Spirit of Light, Raava and learning of the danger to the world Wan then got the power of Wind but the power had to be held by Raava who would them swap the elements when Wan needed it. during training Wan realized he needed the other elements so he then sought out the Lion Turles who bestowed Water and Earth, how in the episode in that order.
So the Avatar Reincarnation Cycle of Fire, Wind, Water and Earth is the same order in which the Wan and Raava got the elements.