I gather that "how far back does it go" may be unanswerable, so please let me commend you for "can we document", which is answerable.
More can be written on the subject, but I believe the immediate answer to your question is here by /u/Algernon_Asimov .
If you want to read more, including background and spread, the "Calendars and timekeeping" FAQ page, in the section "Weeks, weekdays, and weekends" (in the app, the "#" anchor doesn't work, so find it in the middle of the page). The discussions appear to be in the top four and the bottom. Even the one on "fortnight": that's the one that had the link above, due to questions about the connection between 14 days versus 7 days and 28ish days (lunar cycle).
This is not to discourage discussion. Questions, data, and debate are welcome.
I think you can get a pretty good understanding of the history of the week in my long answer:
Rather than thinking of weeks as a natural division of a lunar cycle (the lunar cycle is slightly more than 28 days, after all, so over time a full moon would move from Sunday to Monday to Tuesday to Wednesday, as there's no "leap day" keeping the schedule regular), I think it's more important to think of the week as man-made cycle dividing regular events, most often markets and/or supernatural events.
The week that we use today is a combination of Babylonian-Egyptian-Greek and Judeo-Christian(-Islamic) influence, as I lay out in that long post. The fact that they both ended up with seven-day cycles may well be related to the 28ish-day lunar cycle; we ultimately don't know. What we do know is that there have been lots of different weekly cycles in place. The Romans, before they adopted a seven-day week adopted from the Egyptians in the First Century CE, used an eight-day calendar adopted from the Etruscans. For a period, both cycles were in use simultaneously in the Roman Empire, until Christianization finally killed other calendars permanently. In many places in sub-Saharan Africa, there are four-, eight-, or sixteen-day market cycles, many still in place though losing out to the seven-day cycle. Almost everyone with any sort of market economy seems to have a man-made unit of time between the natural solar day and lunar month, but these generally range from about four to ten days (though I've seen as short as four and as long as sixteen).
As for when it started, the main researcher I relied on argued there's little evidence of a seven-day week with six days of work and one day of rest for the Jews before the Babylonian exile. Not to say it didn't exist, just that we have limited evidence of it, mostly coming down to how secular scholars date various books of the Bible. I personally think we can assume, based on the evidence we have, there was some seven-day cycle in the First Temple Period, before the Babylonian exile of 586 BCE . However, this is part of his argument that the Hebrews ultimately picked this up from an older Assyrian/Ancient Near Eastern seven-day cycle, where one day was set apart every seven days because of bad omens, though these were actually still tied to the lunar cycle--they had occasional "leap days". This broader Ancient Near East tradition might be older still, but how much older we really can't be sure.
Suffice to say, it's old, at least to the return from the Babylonian exile, and in my view quite likely older.