According to the "Klingon Art of War" by Keith R.A. DeCandido, the Klingon gods were surprisingly mortal. They apparently lived in a 'great tree'. One of them made first contact with the Klingons some 2-3000 years before the time of Kahless (and approximately a thousand years before the arrival of the Hur'Q). Their initial demand was for food, which the Klingons provided in return for being shown simple building techniques. Several hunters were killed in the process, but the gods evidently had the power to revive them.
Over time, the gods took over various villages and began demanding greater and greater "tributes" but seemed unwilling to share additional technology with the Klingons. Eventually the Klingons got tired of fighting proxy wars on behalf of the different godly factions and went up to the great tree and killed them all.
THE GODS AND THE GREAT TREE
Enemies also change with time. Once, thousands of wars before Kahless was born, Klingons worshipped gods who ruled from atop the qo’Sor, the Great Tree of the World, which once stood on the plains of Balduq. These gods required tribute and sacrifice, which the Klingons of the time provided, and ritual, which they followed.
Wa'Joh’a, the first god, came down from the tree to speak to the Klingons. He destroyed a village but allowed the villagers to live. He said he would rebuild the village, making it better than before, but only if the villagers killed ten klongats and burned them before him.
The villagers did as Wa'Joh’a asked, though two villagers died on the hunt for the klongat. In return for doing as he asked. Wa'Joh’a created a new village that was more splendid than the one he had destroyed, brick and mortar replaced clay and dirt.
The first god even brought the two who died back to life.
Beholding Wa'Joh’a’s many gifts, the Klingons of the time gladly bent their knee to him.
Seeing that the Klingons gladly provided worship, other gods came down from the qo’Sor to accept their due.
As time went on, the god's demands increased. Each sacrifice the gods asked of the Klingons was harder than the last and the gifts they gave in exchange more and more paltry.
Worse, the gods squabbled. Each god claimed a village, but some gods were jealous and demanded larger villages with more pious worshippers. The gods fought among themselves, great battles that devastated the villages over which they fought.
The Klingons became less and less interested in bending their knees to these petty, capricious creatures, or in doing their bidding.
Eventually, there came a day when Kortar the Mighty and his mate Baka visited each village and made a call to arms. After a full turn, the pair had recruited a hundred warriors for a charge across the Balduq Plains. They climbed the qo’Sor and slew the gods, and then they destroyed the great tree.
Given that this description certainly sounds a bit like the gods were alien invaders, I asked my good friend Keith DeCandido whether this was his intention. The short answer is that it wasn't but that he does consider that a plausible version of events.
Q. In the Klingon Art of War, I got the impression the Klingon gods
were alien invaders. Was this intentional?
KRADeC: My only intent was to make them mythological. Yours is one of many valid interpretations of those myths. :)