How far back in time could you go, before modern English becomes unintelligible to inhabitants of the British Isles?

Let's make some assumptions. One is that the modern English speaker is trying to make herself understood - speaking slowly, avoiding new slang words and neologisms, and using simple common language rather than academic words. These are important assumptions.

First of all, while we know a lot about how words were pronounced back 500 or 1000 years ago, there are things we don't know as well - about prosody, intonation, stress, tone, and rhythm. These things would matter a lot to the intelligibility of fast-flowing conversation, but not as much when one is speaking slowly and deliberately.

In linguistics, the word "register" means the type of language you would use in particular social settings. Among friends you are very likely to use a lot of slang, in-group lingo, curse words, and jokes - called "informal register". At a job interview you would use a "formal register" to try to prove that you are respectful and well-educated - you might throw in a few big Latinate words, for example, and a more complex syntactical style. Both of these might cause problems for a centuries-old interlocutor, because slang, cultural references and in-jokes obviously change pretty quickly over the course of history, but also because a lot of the academic language of Latin and Greek words entered the English language during the 16th - 19th centuries. In fact, as Otto Jesperson claims, these words were adopted by scholars so enthusiastically in that period that they "stunted the development of native forms".

The unnatural state into which the language has been thrown by the wholesale adoption of learned words is further manifested by the fact that not a few of them have no fixed pronunciation; they are, in fact, eye-words that do not really exist in the language. Educated people freely write them and understand them when they see them written, but are more or less puzzled when they have to pronounce them.

Jesperson gives the example of "gaseous", but that has resolved itself now in the last 100 years. "Hegemony" is a better example these days.

So we would be aiming for a middle register of simple, common words. The advantage of this is that most of these words have existed in the English language since at least the 1300s. Only a few common words (like "dog") entered the language after that.

The next assumption is that we are speaking to an inhabitant of the British Isles who speaks English. Remember that the further back in history you go, the greater the share of Celtic language (Welsh, Gaelic, Irish, Pictish, Cornish, Manx) speakers you would have on the islands. There were also other Germanic languages - Norn, spoken in the Orkney and Shetland islands, and Scots, spoken in lowland Scotland then as now. In Ireland you had Fingalian and Yola.

So here is my answer. Someone from Shakespeare's time (early 1600s) would have little trouble understanding you. It would be about the same level of comprehension you might have for someone speaking Scots if you are from Georgia. But go another hundred years back from that and you're going to start encountering some real problems with your vowels. That's because of the Great Vowel Shift. This happened when the pronunciation of some vowels started to change in about 1400, forcing the other vowels to also shift in order to stay distinct from the ones encroaching on their phonetic space. By 1700 almost all of the vowels in the language had changed. For example, the vowel that was pronounced like in "leek" became like the vowel in "like". So by the time you get back to 1500 or 1400 it will start to sound like people are speaking with a really weird and hard to understand accent. It will start to sound more like Dutch.

(Edit: to get a better idea of how these vowel shifts work, check out the Northern Cities Vowel Shift, which has been happening for the last 150 years or so in the area around the Great Lakes. Raising and tensing of /æ/ is the most noticeable example if you are not from the midwest - "cat" is pronounced like "kyet". Here is a video of a linguist, William Labov, discussing it.)

Then you'll hit a real wall in about the beginning of the Middle English period (1150-1400). That is because that was the period when French vocabulary was being imported wholesale into English. Common words like beauty, money, sport, honest, war, table, chair, and thousands of others were imported in this period. You probably wouldn't even know what the English words they displaced were.

Before that you are into Old English, which would be very difficult to understand, though people often overestimate the difficulty. It would be unintelligible, but probably easier to pick up than a foreign language. People often look at Beowulf as their example of Old English. But Beowulf is written in a poetic style that would have been abstruse even at the time it was composed. To get a better feel of prosaic Old English, have a look at the Anglo-Saxon Chronicles, and keep in mind that the þ character is now written "th" and the "sc" digraph is now written "sh".

Brytene igland is ehta hund mila lang and twa hund mila brad, and her synd on þam iglande fif geþeodu, Ænglisc, Brytwylsc, Scottysc, Pihttisc and Boclæden. Ærest wæron buend þyses landes Bryttas, þa comen of Armenia, and gesæton suþonwearde Brytene ærost.

Translation:

The island Britain is 800 miles long, and 200 miles broad. And there are in the island five nations; English, Welsh, Scottish, Pictish, and Latin. The first inhabitants were Hi the Britons, who came from Armenia, and first peopled Britain southward.

TL;DR: You'd probably get to about 1400 and be able to scrape by.