The law of relating the story of the Exodus in the evening has been observed by our ancestors ever since the actual Exodus itself. In the early years, when Israel was still in the desert and when they first entered Eretz Yisrael, there was no fixed format as there is today.
Apart from the 'Egyptian Hallel' which was said while the people were still in Egypt, each father decided for himself how to tell the story to his son. When the 'Men of the Great Assembly' fixed a set pattern for prayers and blessings, they also established a fixed version for the Haggadah.
At the time of the Mishnah we find that there was already a fixed format for "mah nishtanah", and for the analytical midrash study beginning, "arami oved avi".
In the course of time, midrashim were added to the basic version, and the present version was more or less complete and fixed in the time of the Geonim.
One question had been altered before that, with the destruction of the Temple - the one asking why on other nights we eat meat cooked any way we wanted, but this night only roasted - because we no longer had the Pesach sacrifice. Likewise, the Aramaic "ha lakhma anya" was introduced, with the words 'this year here, next year in Eretz Yisrael!'
Similarly, songs and poems have since been added, but the basis of the Haggadah was fixed by the 'Men of the Great Assembly'. (Talmud Berakhot 33.)