Birkat HaMazon
Pre Tannaim and Amoraim
Since Birkat HaMazon is already a mitzvah from the Torah "ואכלת ושבעת וברכת", there are very early versions of Birkat HaMazon. Moshe Weinfeld1 says that one of the sections found from קומראן is Birkat HaMazon and has the same components as ours: מזון, ארץ, ירושלים and הטוב והמטיב.
Tannaim and Amoraim
In the Bavli it says that ברכת הזן, הארץ and בונה ירושלים were נתקן already during the biblical time:
אמר רב נחמן: משה תקן לישראל ברכת הזן בשעה שירד להם מן, יהושע תקן להם ברכת הארץ כיון שנכנסו לארץ, דוד ושלמה תקנו בונה ירושלים. דוד תקן על ישראל עמך ועל ירושלים עירך, ושלמה תקן על הבית הגדול והקדוש, הטוב והמטיב ביבנה תקנוה כנגד הרוגי ביתר.
However, in Bemidbar Rabbah it says that they said ברכת הזן until they came to Eretz Yisrael, when they came to Eretz Yisrael they added ברכת הארץ, when ירושלים was destroyed they added בונה ירושלים:
שנו רבותינו עד שלא נכנסו לא"י היו מברכין ברכה א' הזן את הכל משנכנסו לא"י היו מברכין על הארץ ועל המזון משחרבה הוסיפו בונה ירושלים משנקברו הרוגי ביתר הוסיפו הטוב והמטיב.
According to both the Bavli and Bemidbar Rabbah ברכת הטוב והמטיב is later and was נתקן when הרוגי ביתר were buried. But, R. Eliezer, R. Yishmael and R. Yossi HaGelili mention the berakhah and they were before הרוגי ביתר. According to the Yerushalmi and other כ"י of the Bavli the berakhah was only נקבע when הרוגי ביתר were buried and it is much earlier berakhah. The Rambam says that the berakhah was נתקן by חכמי משנה.