Roman myths
What appears to be the oldest story of a "werewolf" is actually an ancient Roman myth. In 1 AD, Ovid wrote the Metamorphoses, in which there is the tale of King Lycaon (the origin of the word Lycanthrope) who greatly offended the gods by serving human flesh to them. Jupiter punished Lycaon by transforming him into a wolf. This myth lacks modern features of werewolf tales, in particular the idea of changing back and forth. Nevertheless, it likely set in motion the idea of "man becoming wolf".
Modern resurgence of werewolf legends
The first supposed "werewolf" sighting was in the countryside between the towns of Cologne and Bedburg in Germany in 1589. A pamphlet was drawn up by those who claimed to have witnessed it, which was then distributed around the towns. While the pamphlet was intended to be a public service and therefore non-fictional in spirit, it was of course describing a dubious event and hence a work of fiction in some sense — just not for entertainment. Its contents explicitly described a creature changing from wolf to man during the dead of night.
The supposed werewolf turned out to be a man by the name of Peter Stubbe, who was executed for a string of gruesome murders (which he really did commit apparently).
For many years, people in the neighbouring towns really did believe that Stubbe had been changing from wolf to man in the night. This is likely the origin of werewolf stories as we know them today. There were earlier wolf-man claims in France that also anticipated the modern notion of werewolf (in particular, claims preceding the executions of Pierre Burgot and Michel Verdun), but the content of the Cologne / Bedburg pamphlet is more akin to our modern perception of "werewolf" than what was reported at the time of the French incidents.
The "Werewolf of Bedburg" pamphlet, which was translated into several different languages, appears to have spurred Europe's fascination with werewolf lore. In particular, it seems to be the source of the idea of werewolves changing back and forth between human and wolf form.
"The Lay of the Bisclavret"
Now, if you really want the earliest werewolf story written for entertainment that anticipates some features of the "modern" werewolf", I believe we should look to "The Lay of the Bisclavret", an 12th Century lai by Marie de France. It predates the Bedburg incident, but grew in popularity after it, partly because Bedburg prompted interest in werewolves and partly because of the eventual advent of the printing press and the availability of translations.
According to The Essential Guide to Werewolf Literature by Brian J. Frost, this was the first true European werewolf fiction. The protagonist, a baron from Brittany, transforms into a wolf once a week due to forces beyond his control.
"The Man-Wolf" and "Hughes the Wer-Wolf"
Finally, getting even closer to modern werewolf fiction are Leitch Ritchie's short story "The Man-Wolf" (1831) and Sutherland Menzies' story "Hughes the Wer-Wolf" (1838). Fueled by the rise of Gothic horror in the late 1700s (e.g. the works of Horace Walpole), Ritchie and Menzies turned to myth, folklore, de France's lais, and dubious recordings of werewolf phenomena such as the Bedburg incident to create a new home for the modern, full-moon transforming werewolf in fiction.
All of these precede the 1839 Frederick Marryat short story mentioned in the comments below the original question, although Marryat did contribute the first female werewolf to the literature.
(Acknowledgements to @GorchestopherH for some valuable assistance with this!)
