Published in "Fantastic Universe" December 1957.
They had been cramped for space, him and his people. Obviously this new age had solved the problem better.
"You're a fascinating person," the girl said. "I've never met anyone like you before. Tell me your story again."
The man was short and stocky, with Asiatic features and a long, stringy mustache. "The whole story?" he asked. "It would take a lifetime to tell you." He stared out the window at the yellow sun and the red sun. He still hadn't gotten used to seeing two suns. But that was minor, really, when there were so many other things he had to get used to.
A robot waiter, with long thin metal tubes for arms and legs, glided over. When he'd first seen one of those, he'd thought it was a demon. He'd tried to smash it. They'd had trouble with him at first.
"They had trouble with me at first," he said.
"I can imagine," said the girl. "How did they explain it to you?"
"It was hard. They had to give me the whole history of medicine. It was years before I got over the notion that I was up in the Everlasting Blue Sky, or under the earth, or something." He grinned at the girl. She was the first person he'd met since they got him a job and gave him a home in a world uncountable light years from the one he'd been born on.
"When did you begin to understand?"
"They simply taught all of history to me. Including the part about myself. Then I began to get the picture. Funny. I wound up teaching them a lot of history."
"I bet you know a lot."
"I do," the man with the Asiatic features said modestly. "Anyway, they finally got across to me that in the 22nd century - they had explained the calendar to me, too; I used a different one in my day - they had learned how to grow new limbs on people who had lost arms and legs."
"That was the first real step," said the girl.
"It was a long time till they got to the second step," he said. "They learned how to stimulate life and new growth in people who had already died."
"The next part is the thing I don't understand," the girl said.
"Well," said the man, "as I get it, they found that any piece of matter that has been part of an organism, retains a physical 'memory' of the entire structure of the organism of which it was part. And that they could reconstruct that structure from a part of a person, if that was all there was left of him. From there it was just a matter of pushing the process back through time. They had to teach me a whole new language to explain that one."
"Isn't it wonderful that intergalactic travel gives us room to expand?" said the girl. "I mean now that every human being that ever lived has been brought back to life and will live forever?"
"Same problem I had, me and my people," said the man. "We were cramped for space. This age has solved it a lot better than I did. But they had to give me a whole psychological overhauling before I understood that."
"Tell me about your past life," said the girl, staring dreamily at him.
"Well, six thousand years ago, I was born in the Gobi Desert, on Earth," said Genghis Khan, sipping his drink.