It isn’t all that often that the origin of a phrase can be directly pinpointed. With ‘friends with benefits’ we have a clear source – Alanis Morissette’s 1995 song Head Over Feet:
You’re the best listener that I’ve ever met
You’re my best friend
Best friend with benefits
What took me so long?
It may be that friends with benefits or fwb began life as street slang or on message boards before 1995 but, if it did, I can’t find any record of it. At the very least we can say that Morissette brought the expression to the public’s attention.
The phrase was restricted to the young for a few years. In the late 1990s it began to be used on Usenet newsgroups, which, if you’ve forgotten them already, were a form of prototype social media.
Friends with benefits was a widely enough used expression in the USA by 1999 for an Oregon University student group to use it as the title of a play they performed in November that year.
The phrase and its fwb abbreviation are now used around the world, although still largely by those who might consider participating in such an arrangement.