As with basically anything else in ancient history, there's nothing so cut and dry about this. The Romans place the story of Romulus and Remus founding the city in 753 BCE. At that same time, records from Mesopotamia and Egypt were already approaching 2000 years old. So this question differs wildly for each place. There's also the issue of lost information. According to Roman tradition, many of the earliest histories, chronicles, and documents were lost in the Celtic sack of Rome in the early 4th century BCE, so any history that the Romans might have recorded prior to that was lost and the major sources that we're aware of today only start appearing in the 3rd century or later, with writers like Polybius.

So according to the Romans themselves, they had factual histories prior to the 3rd century, but they were mostly lost and the Romans became reliant on remembered traditions for everything prior to the Celtic sack. If anything, mass loss of records like this might have caused historic events and figures to become legendary and mythologized in the absence of a set version of the story.

We see something similar in Greek history. At the end of the Bronze Age, the Mycenaean Greek culture collapsed. Their writing system (Linear B) was forgotten by Greek speakers and written accounts in Greek language do not resume until sometime between 800-600 BCE. Even then, some of the earliest long-form examples are myths and legends, like the Homeric Epics or the works of Hesiod. In these highly mythologized accounts, they treat myths like history and place the age of the classic mythological heroes in the Mycenean period and the intervening "Dark Age" years between 1200-800, when no written records exist. In the Greek world, the first real attempts to record factual history were by the "logographers," like Hecataeus of Miletus or Xanthus of Lydia, beginning in the 6th century, who were not always successful in (or even trying for) separating myth from fact. That would probably make Herodotus the first known Greek history to intentionally try and exclude unconfirmable mythology.

Despite these examples of clearly historic documentation in the 5-3rd centuries for the Greek and Roman world, you still have people like Livy or Diodorus Siculus including myths and stories of the gods at the beginnings of their histories in the 1st centuries BC/CE.

Meanwhile, attempting to determine the earliest factual document of history in general is even less precise. Around 1700 BCE, Mesopotamians tried to compile a list of all of the kings in their remembered history. This was roughly 1500 years after the first cuneiform writing was invented. This list included both relatively well documented figures who ruled for very realistic lengths of time, like Sargon of Akkad (40 years), alongside kings who ruled for impossibly long periods, like Alalngar who ruled for 36,000 years. Some, like Alalngar, are obviously mythical, but for others it isn't so obvious. Ur-Zabba, supposedly a contemporary of Sargon, is said to have ruled for 400 years

The most famous king on the list also serves as an example of this dichotomy in one figure. Gilgamesh, best known for his impossible mythic feats as a hero of an Epic, is also considered to be a historical king. In the Epic of Gilgamesh and other legends, he is a giant, divinely blessed, hero who slays monsters and travels to the underworld. At the same time, he is mentioned in the inscriptions of known historical kings as another king in their world at that time, c. 2800-2500 BCE.

Basically, ancient history is a muddled mess of sources that include myths and legends in the contents everywhere from 0-100% of the time. It depends vastly on the scope of the time they want to cover, they opinions of the author, their subject matter, and the sources available to them at the time. There is no point in time when you can say that people, anywhere in the world, stopped including myths in their history books. After all, there are still elementary school students in the US today being taught that George Washington chopped down a cherry tree. The biggest thing that has changed, in my opinion, is the quantity of written records and the length of time that has been recorded in writing. The more people have written down as current events, the more sources historians have access to when creating their histories. As we've learned more about archaeology and science, we're also able to explain prehistoric time in other ways with more concrete details. Coincidentally, those are the same tools that we use to determine what in ancient histories is mythology and what probably isn't.

I'd like to add to /u/Trevor_Culley 's great overview by considering the instructive example of Iranian historiography in late antiquity and the middle ages. Our sources for this basically amount to some not-very-long Middle Persian texts, some inscriptions, and the monumental epic Shahnameh of Ferdowsi.

Now, if most people were to guess they would probably assume the Iranians began to get a solid sense of recorded history with Cyrus the Great or so, but this isn't actually the case, despite extensive interactions with Hellenic literature. The only clearly remembered figure of their distorted and mythicized version of the Achaemenids (known as the Kayanids, a term one could translate along the lines of "the princely ancestors") is Dara, or Dareios III, to whom they traced the ancestry of the founder of the Sasanian empire, Ardaxshir. A few parallels with epithets such as "the long-fingered" being applied to figures in the Shahnameh also exist with Achaemenid kings, but besides that, their history really began to take shape with the Arsacids, or Parthians, to whom most of the big men in the Sasanian Empire traced their ancestry.

This meshes somewhat well with the fact that in the first century of the existence of the Arsacids, prior to the conquest of Fars, they seem to have been pretty hard to distinguish from, say, the Greco-Bactrians. Something seems to have happened as they conquered the West, perhaps due to interaction with remnants of Persian nobility and discovery of the monumental inscriptions and building works of the Achaemenids (the names of which in Persian today still reference mythological figures such as Rustam and Jamsheed).

As far as I know, there was never a time when anyone sat down and tried to sort out what of the stories collected in the Shahnameh were mythical and factual - not before interactions with Western scholars in the modern era and crucially the decoding of the Behistun Inscription in the 19th century. There had been attempts to decode it by Islamic scholars, but not very surprisingly, they were not succesful (the Persian of the trilingual inscription bears more resemblance to Sanskrit than to Middle Persian!). That's not to say that the Persians didn't have historians in the Islamic age (for example, the 14th century historian Rashid al-Din was incredibly influential) but they didn't really have the means to reliably dive into these ancient traditions and sort fact from fiction and fictionalized fact, nor is it clear that they would have been particularly interested in doing so. Works like the Shahnameh transcend mere fact, telling a story about the glory of the ancient Iranians that is, in a sense, true, even if it does not correspond to what we would consider a factual account of history.