According to an often-repeated account that was first published in 1853, the first restaurant was opened in 1765 by a Parisian named Boulanger. Boulanger's establishment on rue des Poulies, near the Louvre, served mostly bouillons restaurants—that is, "restorative broths."
In addition to being a soup vendor, Boulanger was also a guy with a sense of humor: his establishment's motto was the Latin invitation Venite ad me omnes qui stomacho laboratis et ego vos restaurabo. The sentence translates as "Come to me all who suffer from pain of the stomach and I will restore you"—a punning allusion to both the restorative quality of his broths and Jesus's invitation found in Matthew 11:28 "Come to me, all who labor and are heavy laden, and I will give you rest."
Possible Christ complex aside, Boulanger seems to have had some good business sense and some pleasingly restorative broths. His business model took off, and the word for the restorative quality of his broths came to refer to establishments of the ilk of Boulanger's. (The French word restaurants that described Boulanger's broths is from the Latin restaurare, meaning "to renew.")
An aside: all was not happy in Paris in the aftermath. As these restaurants spread and diversified, they infringed on the domain of the traiteurs—caterers who provided cooked food to people lacking a kitchen of their own. The traiteurs (the word translates as "treaters") reportedly took Boulanger to court, but lost, and Boulanger's legacy was secured. The legacy of the traiteurs lived on too: traiteur was borrowed into Italian as trattore, the base of trattoria, a common Italian word for "restaurant" that also graces the edifice of many an American restaurant aspiring to a marinara as good as one in the Old World.
And so goes the story of restaurant the word. But it's of course not the full story of "restaurant" the place you go when you don't want to cook. That topic is too vast for a modest article such as this, but if we keep our focus trained on the words of the English language we see that solely based on the vocabulary of yore, Boulanger's restaurant was not the first "restaurant" by any stretch. The Oxford English Dictionary's Historical Thesaurus lists six words for a "restaurant" between the mid-15th century and the time of Boulanger's broths: eating house, victualling-house, cook's shop, treating-house, suttling-house (which was especially for soldiers), and chop shop.
It seems that we are once again confronted with the English language's swoon for French: restaurant simply sounds more appetizing than any of those. Bon appétit.