That description has more than a little in common with Elizabeth Haydon's "Symphony of Ages", though it's not a perfect match.
Fourteen-year-old Gwydion is transported into a nearly one and one half millennia distant past to the Isle of Serendair by the mysterious Meridion. There he meets and falls in love with the young farmer's daughter Emily. They want to marry, yet when Gwydion goes to propose, he is taken back to his own time by Meridion. The devastated Emily runs away from home in search of him.
Rhapsody, lives in the town of Easton. A former prostitute, she studies to become a Namer and Singer, a profession which gives her semi-magical abilities. When she is pursued by the underlings of her former client Michael, who is obsessed with her, Rhapsody tries to enlist help of two Firbolg, accidentally renaming one of them, a ruthless assassin then called The Brother to Achmed the Snake. Against her will, she is forced by Achmed and his friend Grunthor to accompany them on a journey through the center of the Earth, along the root of Sagia, the Holy Tree.
After a long time the three emerge on the opposite side of the Earth and learn that fourteen hundred years have passed. The lands in which they find themselves were settled by refugees from Serendair, which had been destroyed a very long time ago. Moreover, the original colonists, who sailed there with their king Gwylliam, crossed on their way from Serendair the meridian and thus became immortal (no longer aging, but still able to be killed or die of illness). Their descendants born already in the new lands are only extremely long-lived, though.