Scholars quibble over "The First Novel," but most agree that the genre grew out of medieval romances, beginning in the very late 1600's and early 1700's.
Travelogues also played a role in the novel's birth. These were popular, often highly exaggerated accounts of voyages and exploration. Jonathan Swift's Gulliver's Travels came out of this tradition.