During Old Night, the people of Strela fragmented into many different tribes, each formed around a strong warlord, a Knyaz. The Knyazi would often make war among themselves, each fighting for supremacy in a world where supremacy no longer meant anything.
As time moved on, the descendants of a particularly influential Knyaz would begin referring to themselves as the sons and daughters of this tribal leader, seeing their ancestral blood as more important then their immediate family - together, they would claim the right to bear the sigil of that ancient Knyaz, and such conglomerations of individuals and families went on to call themselves Houses, pooling their resources to remain in power over several generations.
When Zalmoxite Platers finally returned to Strela after fifty generations, meaning to begin trading more advanced weaponry for men and food, the Houses stepped forward to start this new relationship with the off-worlders. With these guns, they began to conquer surrounding tribes who had not had the chance to buy the weaponry, and thus were born the early Strelian Nations.
As time moved on, the Platers bought ever more powerful artefacts and vehicles with them, and full Nations went to war with each other, the escalation causing ever more destruction and devastation.
When Kozja took control of Darzala, the Houses of the nobility opposed him at first. Afraid of loosing their power, they saw in him change made manifest. However, as his Genetnik Huszars pushed his conquests ever further, the nobility found that those who resisted Darzalas the most were generally those that lost the most members during the repression culls; conversely, the initial Darzalan Houses that had supported his claims to power fared best in his new government, where a parliament of nobles were even given the right to make political decisions in the Darzalan nation. As the pattern became apparent, more and more Houses decided to submit to Darzala, even before the Huszars were unleashed upon their borders, and soon all of Strela was under Kozja's control.
When Kozja became sole ruler of the Jagellonic System, the noble Houses once more saw a threat to their new power that they held in Strela's parliament. Rather then let the Vostalan and Zalmoxite magnates be granted seats by Kozja without any supervision by the existing members of parliament, the noble Houses asked Kozja to allow them to "adopt" magnates, thereby making them integral parts of the existing Strelian Houses. The Alabaster Prince - seeing an opportunity to increase his realm's cohesion - granted them this right, and increased the size of the old Darzalan parliament to incorporate representatives of the nobility from both planets.
On Kozja’s return from his time at the side of the Emperor in the Solar System, he found that Strela’s aristocracy had naturally continued their new tradition of adopting off-worlders, expanding that definition to the IX Legion. By this time of course, all pretence of keeping the Houses in a single blood line had been abandoned - instead, the Nobility had begun choosing new members according to shared values, such as loyalty, courage or tolerance. These new Patrician Astartes had started going to balls, presented as exemplars of the new order in which Strela would move forward as a major power in the galaxy.
This, of course, suited Kozja’s plans perfectly - three lessons did he learn from his lessons on Terra and Luna: first, the Legiones Astartes were fundamentally superior to mortal humans; next, his Fathers’ talents and his own could help humanity finally leave Old Night behind it and once more flourish grandiose and dominant; last, but definitely not least, his brothers and their sons could not be trusted. By learning the ways of the court, the Legionaries of the IX would be moving to the forefront of the political arena - a necessary step on the way for Kozja to help mankind evolve and grow into its full potential.
The Heraldic Houses of Strela followed the Warbringers into the stars. Though their existence skirted the very edges of the Emperor’s ban on Warrior Lodges, the formation of the Warbringers that was subject to most scrutiny was the Bogatyry. The Nobles of the Jagellonic system - whether Astartes, or officers of the Novadeka or simple civilians - were therefore free to mingle with the aristocracy throughout the galaxy, weaving a web of relations that should last for decades, if not centuries.