Well, let's see if I'll have to censor my own link here....
Online Etymology Dictionary
And yes, it appears that the earliest usage in print was around the early 16th century, but it was around much, much earlier... its origins are in doubt, as you can see when you look it up at that site, and it's closely related (in some derivations) to "fr*g", of course.
The thing to remember if using cursing in any fiction is to balance what is considered a curseword or swearing now and what was considered so at the period you're writing about. Words we view as such may simply have been the proper term for something in the original language and time, yet if they hit a modern reader as inappropriate, it can be jarring. It's a fine line one has to walk between the two....