Apart from regional variations, you wouldn't have much trouble until you got back to the 16th-17th centuries. This was the time of the great vowel shift, when many of the vowels were pronounced differently. Before and during this process, the language didn't sound like now, and there would be some issues of comprehension. As a written language though, it's mostly the same as now. From the Second Quarto of Hamlet:
To be, or not to be, that is the question,
Whether tis nobler in the minde to ſuffer
The ſlings and arrowes of outragious fortune,
Or to take Armes again in a sea of troubles,
And by oppoſing, end them, to die to sleepe
No more, and by a sleepe, to ſay we end
The hart-ache, and the thouſand naturall ſhocks
That flesh is heire to;
Still, it would be the same language, so you'd get by if you all spoke slowly. You'd have to go back to before the Norman Invasion of 1066 to encounter a completely different language. It would sound like gibberish, as would your English to them. Here are the first few lines of Beowulf:
Hwæt! We Gar-Dena in gear-dagum
þeod-cyninga, þrym gefrunon,
hu ða æþelingas ellen fremedon!
Oft Scyld Scefing sceaþena þreatum
monegum mægþum meodo-setla ofteah;
egsode eorl[as] syððan ærest wearð
feasceaft funden; he þæs frofre gebad,
weox under wolcnum, weorð-myndum þah,
oðæt him æghwylc þara ymb-sittendra
ofer hron-rade hyran scolde,
gomban gyldan. Þæt wæs god cyning!
In between, there's the period of Middle English, which is Old English morphing with French to eventually form Modern English. Unlike Old or Modern English, there was no official version of this, because the government elite spoke and wrote in French (or Anglo-Norman, to be precise). We have literary sources, however, of which the most famous is Chaucer's Canterbury Tales. The vocabulary is very different, but it's still easily recognisable as English:
WHAN that Aprille with his shoures soote
The droghte of Marche hath perced to the roote,
And bathed every veyne in swich licour,
Of which vertu engendred is the flour;
Whan Zephirus eek with his swete breeth
Inspired hath in every holt and heeth
The tendre croppes, and the yonge sonne
Hath in the Ram his halfe cours y-ronne,
And smale fowles maken melodye,
That slepen al the night with open ye,
So priketh hem nature in hir corages:
Than longen folk to goon on pilgrimages,
Source: A History of the English Language, edited by Richard Hogg, David Denison
Edit: forgot to give an answer to the question: You could talk to Shakespeare easily, though both of you would think the other sounded weird. With Chaucer, it would have to be slow and with a lot of misunderstandings, maybe like an Italian and a Spaniard talking today. With whoever wrote Beowulf: That would be like Amy Adams talking to the spaghetti monster in Arrival.
Edit2: The word 'weird' is a Shakespearian innovation, from the three witches of Macbeth, and it comes from the Anglo-Saxon wyrd, which means faith or destiny.
Probably early 1500s.
see answer by u/texspeare: https://www.reddit.com/r/AskHistorians/comments/25c3t1/what_is_the_furthest_year_i_can_go_back_in_time/
A few more posts that you may find interesting:
How far could I go back in time and still be able to understand period English and communicate effectively? - /u/traininthedistance kicks off the subject with a brief introduction to the timeframes of various Englishes. Note the reference to The Canterbury Tales vs Sir Gawain and the Green Knight, which leads us to...
How is it that I can mostly read "The Canterbury Tales" in the original, but "Sir Gawain and the Green Knight," written at roughly the same time and in the same country, is mostly unintelligible? - featuring /u/sunagainstgold and several other users in a long conversation on English in this period
If you took an English person from 1314 and an English person from 1114 and got them to talk to each other would they think each other's speech patterns were odd? If "yes" would they still be able to easily understand each other? - featuring /u/popisfizzy and others
If I were to be transported to Ancient England, how hard would it be to understand Olde English? - includes links and readings of Old and Middle English
A couple of more general posts:
FAQ entry What is the furthest year I can go back in time to England and be able to communicate with people? - featuring /u/texpeare and others; features a few sound samples
What's the furthest I could go back in time in, say, London and still generally understand the English being spoken? - featuring /u/jimthewanderer