This is a short story that I read several (5?) years ago. I don't believe it was new, but I don't remember how old it was, either. If I had to guess based on style, I would say that it was probably written sometime in the 80s or 90s.
The protagonist comes across an old coin that isn't from anywhere -- at least, not from anywhere that he or coin dealers or historians can identify. Somehow, he gets the idea that the coin is from another, parallel reality, and he decides that it would "want" to go home, if it could. He starts to travel, and whenever he comes to a decision about where to go next, he lets a coin toss (using that coin) decide the issue. The transition from one reality to another is gradual, not sudden like going through a portal, more like elements of reality being gradually replaced as he goes from one place to another.
Eventually, he does get to the place where the coin originated, at which point the plot (if I'm recalling correctly) devolves into a rescue-the-princess-from-the-clutches-of-the-evil-king/sorcerer/vizier scenario.
The parallel universe that the coin came from is full of deserts and has an "Arabian Nights" flavor. I think the protagonist meets a djinn/genie in the desert when he first gets to the right universe, but that could be something I'm mixing in from a different tale.
I'm drawing blanks on more specific details, but hopefully someone will recognize it from the above.