We know little of gnollish origins, and the gnolls know even less. But with enough examination, we can come to a few conclusions. First, gnolls are one of the oldest races on Abir Toril, entering the scene sometime during the Age of Thunder. A few things point to this idea. First; the dawn of civilization occurred -35000 Dale Reckoning and the first written instance of gnolls is in -30400 DR. When gnolls of an apparently large civilization known as Urgnarash summoned evil spirits of pestilence known as Marrashi to destroy and lay waist to a great amount of the Avian creator race’s society. Grand History of the Realms pg8.
This may seem trivial at first, until one realizes this is far, far before any other savage humanoid came into existence, and even before the Giant-Father bore the first of the Giantkin. Also, it states in Grand History that clerics of Yeenoghu were responsible for the attack.
Why is this significant? It means gnolls are far older than this. It has been established canon that gnolls worshiped Gorelik throughout much of their primitive history, and Gorelik first taught them how to domesticate the mighty Hyenadon. (dire hyena) It took some time before Yeenoghu was worshiped as a gnoll god, when he usurped power over Gorelik for a number of reasons. The primary being that Gorelik could not claim to be the creator of gnollkind, as even the earliest gnoll myths do not tell of their creator. The second reason was that Yeenoghu’s priests could become true clerics with the ability to control dead and weave more potent spells, rather than the weaker and more primitive shaman and Witch-doctor classes that were available to Gorellik’s priests. Monster Mythology pg83
It is possible, that this is an inaccuracy caused by scholars ‘filling in the blanks’ with figures they knew of. A few things imply this idea:
First, the Marrashi are Lawful Evil outsiders from the Nine Hells. While not true Baatezu they will work for them, and are known as one of the few creatures of Baator that are not under Baatezu dominion. Yeenoghu is a demon and is in fact the enemy of the Marrashi. This leads one to believe that a Lawful Evil god was responsible for conjuring this army. Possibly even the original gnoll creator god. Second, Yeenoghu is powerful, but he’s not that powerful. He’s still a demipower and it is unlikely he could conjure enough Marrashi that it would lay waste to an immensely powerful nation of beings. Third, this may be reference to the rumored, ‘ancient flind kingdom’ that is mentioned as a topic of scholarly debate in a few 2nd ed sources.(Reference coming, will remove if can’t find the reference I’m thinking of.)
From gnolls themselves, we only have a single canonical story on gnoll origin. This comes from the words of Krote Word-Maker, Shaman of Gorellik to the Burnt Paw tribe, “Me gods gave my people everything in the world. Everything we can see belongs to the gnolls.” This is only notable that it implies ‘gods’. Also, his tribe did not worship Yeenoghu. Likely he’s referring to the giantkin deities that many gnolls are said to have worshiped. Harpers 07: Soldiers of Ice, pg49
Non WOTC/TSR published material: The march (A conglomeration of tribes and clans) known as the Fleshrakers would would play a significant role in the Underdark when they would later become the Deep Gnolls after being genetically manipulated by devils