Probably pretty far, further than an English-speaker could go! There are some changes in pronunciation but nothing as major as the Great Vowel Shift in English, and no major event like the Norman Conquest that radically altered the language. So while Old English is unrecognizable, a completely foreign language, Old French is clearly similar although not quite perfectly understandable to a modern speaker.

“English readers of seventeenth-century French texts will have observed that some words now have a different meaning, while others have fallen into disuse, and they may also have noticed vestiges of older grammatical constructions today considered impossible, incorrect or at best archaic and quaint. Such differences will strike the reader even more forcibly as he goes further back, through the French of the sixteenth century to that of the Middle Ages. The French reader, too, finds the language increasingly opaque and baffling as he goes further back through its abundant literature. Indeed, unless he is a specialist, he will have to read such masterpieces as the Song of Roland and the Romance of the Rose in modern translations.” (Rickard, pg vii)

Here is an example of Old French from the 12th-century Song of Roland (all of these examples are also in Rickard’s book):

Dist Oliver: ‘Sire cumpainz, ce crei,

De Sarrazins purum bataille aveir.’

Respont Rollant: ‘E Deus la nus otreit!

Ben devuns ci estre pur nostre rei:

Pur sun seignor deit hom susfrir destreiz

E endurer e granz chalz e granz freiz,

Si.n deit hom perdre e del quir e del peil.

Rickard translates this as:

Oliver said: ‘Sir companion, this I believe,/ We may do battle with the Saracens.’/Roland answers: ‘May God grant it to us!/Here we must stand for our king:/For his lord’s sake, a man must suffer hardship/And bear both great heat and great cold,/ And also lose both skin and hair.

The biggest difference is that Old French still has traces of the Latin case system. Latin had 5 cases, so you could tell the role of each word in the sentence by its case ending, and word order was relatively unimportant. Old French still had the nominative case (the subject of the sentence), and all the other Latin cases had collapsed into the oblique case (the direct and indirect objects in the sentence). You can see an example of this here - “sire” is nominative but “seignor” is oblique. They come from the Latin nominative “senior” and accusative “seniorem”. Since there are still two cases, word order is a bit freer than in modern French, but not quite as free as in Latin.

Here’s an example from a prose work (so we don’t have to worry about metre and rhyme scheme influencing word order), the Conquest of Constantinople from the 13th century:

Mult s’acorderent li Venisien que les eschieles fussent drecies es nés et que toz li assaus fust par devers la mer. Li François disoient que il ne se savoient mie si bien aidier sor mer com il savoient, mais quant il aroient lor chevaus et lor armes, il se savroient miels aidier par terre.

Rickard translates this as:

The Venetians were unanimously of the opinion that the scaling-ladders should be set up on the ships and that the whole attack should take place from the sea. The French said that they could not operate nearly so well at sea as they (sc. the Venetians) could, but (that) when they had their horses and their weapons, they would be able to operate better on land.

You can still see a bit of liberty in the word order (“s’acorderent li Venisien”, but also the more modern “Li Francois disoient”), different vocabulary (“li” = “les”, “es” = “en les”, “moult” still exists but sounds old-fashioned), and the spelling represents sounds that have since shifted a bit. “Disoient” for example is the modern “disaient”, and would have been pronounced something like “diswent”. In fact all the letters were still pronounced at the time (well, more than they are now, anyway), and the “r” was still trilled, not uvular like it is now.

By the 15th century a lot of this had disappeared. French lost the case system and a lot of the other remnants of Latin. Instead there was a much more rigid subject-verb-object syntax, clearer distinctions between singular and plural forms, and words that had once been in the oblique case in Old French were now just regular words (“sieur” and “seigneur” are doublets - separate words for the same concept). The spelling and pronunciation still would have matched pretty closely, so it’s not quite modern, but French from the 15th century is still pretty easy to understand. Here is part of the 15th-century Cent Nouvelles Nouvelles:

Quand l’yvroigne entendit que encores le failloit enterrer, ains qu’il montast en paradis, il fut tout content d’obeÿr. Si fut tantost troussé et mis dessus le chariot, ou gueres ne fut sans dormir. Le chariot estoit bien atelé; si furent tantost a Stevelinghes ou ce bon ivroigne fut descendu tout devant sa maison.

Rickard's translation:

When the drunkard heard that he still had to be buried before he could go up to heaven, he was content to do as he was told. So he was promptly lifted up and placed on the cart, where he soon fell asleep. The cart was well harnessed, and they were soon in Scheveningen, where that good drunkard was lifted down right in front of his house.

Jumping forward to the Middle and Classical French of the 16th and 17th centuries, it’s often said that it probably sounded something like Quebec French sounds today, since that’s when the first colonists arrived in Canada. But of course the colonists often weren’t from the area of "standard" French around Paris, they had their own dialectal pronunciations and vocabulary that weren’t necessarily the kind of French the king spoke. Quebec French also isn’t just fossilized European French, it has evolved in its own way since then. But still, it might be a good approximation of Classical French.

This is the period when the Académie Française was founded (1635). This is also the period where diacritical marks were first used regularly (é, à, ç, etc), but some letters that had become silent were still included in written French, and sometimes authors also started to add back letters that they felt should be there based on Latin etymologies (“parfaict” for “parfait”, or “sçavant” for “savant”, for example).

By the time of the Revolution, 18th century French was beginning to sound more like modern French, with uvular “r”, and silent letters at the ends of words. Spelling and syntax were pretty much exactly the same as they are now, with silent letters being replaced by diacritical marks over the previous vowel. Rickard gives this passage from Beaumarchais, Le Mariage de Figaro (1785):

O bizarre suite d’événemens! Comment cela m’est-il arrivé? Pourquoi ces choses et non pas d’autres? Qui les a fixées sur ma tête? Forcé de parcourir la route où je suis entré sans le savoir, comme j’en sortirai sans le vouloir, je l’ai jonchée d’autant de fleurs que ma gaieté me l’a permis; encore je dis ma gaieté, sans savoir si elle est à moi plus que le reste...

This is pretty much just modern French! After the Revolution, there's almost no difference at all compared to the modern language.

Of course this is all written literature, and it may not represent exactly how people spoke every day. But based on what we know about written French, a modern speaker could certainly communicate with an educated person like Louis XIV. Louis might pronounce a few sounds differently and his vocabulary would be a bit different, but it would be intelligible to a modern person. A modern time-traveller could probably understand French as far back as the 15th century. Going back any further than that, there would still be remnants of Latin that would be more difficult to understand immediately, but with some effort it would still be possible. It would probably be too difficult if you went back to the 12th century or earlier.

My main source for this is:

Peter Rickard, A History of the French Language, 2nd ed. (Routledge, 1989)

Books about the history of French are a bit hard to find in English, but here are some that I’ve used when studying Old French:

E.W. Aspland, ed., A Medieval French Reader (Clarendon Press, 1974)

E. Einhorn, Old French: A Concise Handbook (Cambridge University Press, 1974)