After narrating the stories of the people of Prophets Nuh, Hud, Salih, Lut and Shu'ayb, destroying the disbelievers, saving the believers, warning these nations by explaining the truth to them with the evidence sent in the words of His Messengers, may Allah’s peace and blessings be on them all, Allah said; {Those were the towns that We relate to you} O Muhammad, {their story}, and news, {And there came indeed to them their Messengers with clear proofs,} and evidences of the truth of what they brought them. Allah said in other Ayah, {[And We never punish until We have sent a Messenger (to give warning).]}(quran/17/15), and, {[That is some of the news of the towns which We relate unto you; of them, some are standing, and some have been reaped. We wronged them not, but they wronged themselves.]}(quran/11/100-101)
Allah said {but they were not such who would believe in what they had rejected before.} meaning they would not have later on believed in what the Messengers brought them, because they denied the truth when it first came to them (although they recognized it), according to the Tafsir of Ibn ‘Atiyyah. This explanation is sound, and is supported by Allah’s statement, {[And what will make you perceive that if it came, they will not believe? And We shall turn their hearts and their eyes away (from guidance), as they refused to believe therein for the first time.]}(quran/6/109-110)
This is why Allah said here, {Thus Allah does seal up the hearts of the disbelievers. And most of them We found not...} meaning, We did not find most of the previous nations, {true to their covenant, but most of them We found to indeed be rebellious.} This Ayah means, We found most of them to be rebellious, deviating away from obedience and compliance.
The covenant mentioned here is the Fitrah that Allah instilled in them while still in their fathers’ loins, and taking their covenant, that He is their Lord, King, and that there is no deity worthy of worship except Him,. They affirmed this covenant and testified against themselves to this fact. However, they defied this covenant, threw it behind their backs and worshipped others besides Allah, having no proof or plea, nor support from rationality or by divine law. Surely, the pure Fitrah defies these actions, while all the honorable Messengers, from beginning to end, forbade them. Muslim collected the Hadith, "Allah said, 'I created My servants Hunafa’ (monotheists), but the devils came to them and deviated them from their religion and prohibited them what I allowed them.'" It is recorded in the Two Sahihs, "Every child is born upon the Fitrah, it is only his parents who turn him into a Jew, a Christian or a Zoroastrian."