The basic plot of the story was:
An advanced alien species visits prehistoric earth and engages with early homo sapiens. One of these homo sapiens was, I think, the leader of the tribe visited and they're given a typical caveman name (Can't remember exactly, probably Gruk, or something along those lines) which is later amended with every descendant of this caveman.
The alien species depart and return to earth when it was in the age of feudalism, the Caveman's descendent (Greketh or whatever a stately rendition of the name Gruk would've been to match contemporary naming conventions) now a feudal lord. The alien species depart yet again, I think this time they don't intend to return, and the next stage of the story takes place after humanity has been integrated within the Empire of the advanced alien species.
Greg (descendant of previous men in story) is a high official, and is subordinate to a Galactic Queen. I think it is explained that females of the alien species are able to live 1000's of years whilst the males only have a maximum lifespan of 100 to a 200 years. As the Galactic Queen, who is now relatively old, approaches her death, she relegates more and more of her responsibilities to Greg, and by the end of the story the Galactic queen concludes the story by expressing awe at the rapid evolution and adaptability of Humans, which is significantly greater than her own or any other observed species.