Probably far from the earliest, but Robert H. Wilson's novelette "Out Around Rigel", first published in the December 1931 Astounding Stories and available in a Project Gutenberg etext, is a famous classic. It is the story of an ancient Lunarian spacefarer:
Even from afar off, I could see that it was desolate. Visible now that the water had gone down, the pillars supporting it rose gaunt and skeletal. Towers had fallen in, and the gleaming white was dimmed. It was a city of the dead, under an Earth leprous-looking with black spots where the clouds apparently had parted.
I came nearer to Nardos and the bridge, nearer to the spot where I had last seen Kelvar. Below the old water level, the columns showed a greenish stain, and half-way out the whole structure had fallen in a great gap. I reached the land terminus of the span, still glorious and almost beautiful in its ruins. Whole blocks of stone had fallen to the sand, and the adamantine pillars were cracked and crumbling with the erosion of ages.
Then I knew.
In our argument as to the possible speed of the Comet, Garth and I had both been right. In our reference frame, the vessel had put on an incredible velocity, and covered the nine-hundred-odd light-years around Rigel in six months. But from the viewpoint of the moon, it had been unable to attain a velocity greater than that of light. As the accelerating energy pressed the vessel's speed closer and closer toward that limiting velocity, the mass of the ship and of its contents had increased toward infinity. And trying to move laboriously with such vast mass, our clocks and bodies had been slowed down until to our leaden minds a year of moon time became equivalent to several hours.
The Comet had attained an average velocity of perhaps 175,000 miles per second, and the voyage that seemed to me six months had taken a thousand years. A thousand years! The words went ringing through my brain. Kelvar had been dead for a thousand years. I was alone in a world uninhabited for centuries.
I threw myself down and battered my head in the sand.