The 1907 story "Wie der Teufel den Professor holte" by Kurd Lasswitz, published in English in 1953 as "When the Devil Took the Professor", revolves around the idea of a universe where 3D space is curved and finite, akin to the 2D surface of a sphere; the book SF: The Other Side of Realism has a synopsis on p. 300, available on google books here:
The first of these is the familiar bargain with the devil, who takes a
professor on a tour of the universe in a vessel that exceeds the speed
of light. The professor is a mathematician and suspects that the
universe is curved, as it actually proves to be. So the voyagers
circumnavigate the universe after a flight of several billion
light-years.
This falls more into the category of anticipating an aspect of relativity rather than making use of the theory, because in 1907 Einstein hadn't yet published his general theory of relativity involving curved spacetime.
Searching for "relativity" in the reference book Science-Fiction: The Early Years on google books, earliest story I found that seemed clearly inspired by Einstein's relativity was "Not In Our Stars" (1923) by Conrad Arthur Skinner (writing under the pseudonym Michael Maurice), with the plot outlined on pages 485-486 of that reference, and said to be "a novel about free will and predestination, though told in an odd mixture of comedy of manners, murder mystery, and speculations on Einsteinian space-time." Apparently it involves a fanciful premise in which some meteors "disrupt the earth's orbit and thus affect its situation in time", causing a character to have flashes of visions of the future.
I also searched the followup reference Science-Fiction: The Gernsback Years, and the first story I found that incorporated an element from relativity in a reasonably accurate way was "The Fitzgerald Contraction" by Miles Breuer, published in the January 1930 issue of Science Wonder Stories, the plot summary is on pp. 30-31 of the reference and if you want to read the full story, that issue has been scanned and put on archive.org here. The title is based on an element of relativity sometimes referred to as Lorentz-Fitzgerald contraction which physicists use as a synonym for length contraction in relativity, although the story actually deals with a different element of relativity, time dilation (perhaps the author mistakenly assumed it could refer not only to the shrinking of moving rulers, but the shrinking of the elapsed time measured by a moving clock). According to the summary:
The members of the space team decided to take the ship out on a trial run around the universe, setting automatic controls to bring the ship back to the Moon. The journey took about three and a half days of their time, but when they returned to the Moon, they saw that enormous periods of time must have passed since they departed, for the Moon was dead. The visitors had overlooked the question of time in the Fitzgerald contraction.
And looking at the full text on archive.org, I see it even gives the readers the correct equations for length contraction and time dilation (in units where the speed of light is set equal to 1) on p. 695.