Since 1991, November has been National Novel-Writing Month, when thousands of aspiring writers take up the challenge of knocking out a 50,000-word draft of a novel in 30 days. There's less agreement on whether December should be National Novel-Revising Month. The same goes for which month, if any, should be National Novel-Submitting Month, when successful NaNoWriMowers try to get their novels published.
I don't know much about writing novels, but I have learned one thing to avoid when you're writing that query letter to a professional in the publishing industry. Numerous lists of "don'ts" from publishers and literary agents (such as this one) will tell you: Don't call your opus a "fiction novel."
Fiction novel, the reasoning goes, is redundant, like free gift and completely unanimous, because novels are by definition fiction. This is true, at least by the definition in the Oxford English Dictionary: "A long fictional prose narrative, usually filling one or more volumes and typically representing character and action with some degree of realism and complexity." Even so, fiction novel isn't tautologous in quite the same way as free gift and completely unanimous.
Gift is the noun form of give, which means to transfer from one person to another without expectation of payment, so naturally free gift is redundant. Likewise, unanimous means "in complete agreement," so of course, completely unanimous is a tautology. Novel, on the other hand, ultimately comes from novus, the Latin word for "new," a meaning that's still prominent when we talk about novel approaches to a problem, or the novelty of a new experience. When and how did a disconnection from reality become part of the definition of novel?
This question is especially puzzling when we consider the direction taken by another derivative of novus. In French, novus became nouvelle. Its plural form nouvelles was borrowed into English in the 1400s, but in an indirect way, by translating it into English and keeping its French meaning (a process that linguists refer to as calquing). The English word, you may have guessed, is news — a word that many of us still expect to refer to true facts. In fact, nouvelles was also borrowed directly into English, without calquing, but more on that later.
According to the Random House Unabridged Dictionary, the noun novel came to English in the 1560s from the Italian word novella, which was short for novella storia "new kind of story." This new kind of story was a story told in prose as part of a larger collection of stories, the canonical one being Bocaccio's Decameron, a collection of 100 stories told by 10 characters within a frame story. Though nothing in the word novella requires fictionality, this extra bit of meaning got absorbed into the word just by association. (For a more recent example of the same process, baby mama in African American English simply means the mother of one's baby, but as it moved into General American English, it gained the meaning of "unmarried and probably black.")
The next step in the meaning shift of novel came with the development of the modern English novel in the early 1700s. Like the tales of the Decameron, books like Robinson Crusoe (1719), Moll Flanders (1722), and Gulliver's Travels (1726) hit the three P's of being written in prose and having a plot and a protagonist. They were fictional, too; the difference was that these stories stood on their own, not as part of a collection. But was a little thing like that going to force English speakers to find a new term to name the new form? Heck, no! Instead of coining a novel word, they continued to use the word novel, now with a somewhat more general meaning.
So ever since the word novel has been in the English language, it has meant something fictional — except for a little complication with that French plural nouvelles. In addition to getting calqued into English as news, it was also borrowed directly, with its spelling changed to novels, so that up until the early 19th century (according to the OED), the plural noun novels could refer to items of fiction or fact.
Still, throughout the 19th century and most of the 20th, novel referred primarily to something long and fictional that touched all the bases of plot, prose, and protagonist. The fiction requirement began to crumble with the advent of books that met the three P's requirement but happened to describe true events. It's easy to think of books like this these days: The Right Stuff, The Perfect Storm, Seabiscuit — factual narratives that read like novels.
It may seem like books like these have been around forever, but they haven't. The author who gets the most credit for inventing the form is Truman Capote, with the 1965 publication of In Cold Blood, the true story of a small-town murder and the pair who committed it. Some of this credit was awarded by Capote himself; in an interview that year in Life magazine, he referred to nonfiction novels as "[t]he art form I've invented". More credit comes in the OED's first citation for nonfiction novel, which comes from a 1965 issue of Vogue, in another article about In Cold Blood:
Capote is an experimenter, an adventurer. His newest experiment is In Cold Blood, a unique book, for it is the first non-fiction novel, a precise documentary, in many ways brilliantly composed.
However, it turns out that parts of In Cold Blood are not so factual after all, nor was his claim about inventing the nonfiction novel. Furthermore, he didn't even coin the term nonfiction novel. In a posting to the American Dialect Society email list, Garson O'Toole (better known these days as the Quote Investigator) lists attestations of nonfiction novel from possibly as early as 1931.
Despite all that, the nonfiction novel is a recognized literary genre today, and from that perspective, the existence of the phrase fiction novel should be no more surprising than other retronyms, such as acoustic guitar and film photography. An interesting question, though, is whether fiction novel was a retronym from the moment it was created, or have people been talking about fiction novels since even before nonfiction novels were a thing? It's hard to say. The earliest attestation I've found for fiction novel is from 1930, within a year of O'Toole's possible early sighting of nonfiction novel. It's from an article by Albert Richard Wetjen, telling how he came to write his (nonfiction?) novel Way for a Sailor, published in 1928:
And here I had been trying to write a fiction novel when I had so much actual fact at my fingertips.
However it arose, the phrase fiction novel has a useful function... in the right context. But until nonfiction novels are as well-known as electric guitars and digital photography, you're better off avoiding a perceived redundancy.