Well, there's a lot of dialects of English today (such as in parts of Britain and Australia, and "street" slangs common in many urban areas) that are unintelligible to the bulk of anglophones. It depends on several factors.

• Whether the conversation is written or spoken. Written doesn't have phonological issues (although orthography may be different) but is also fundamentally different in nature.
• How motivated the speaker is to be understood. For instance, if the modern speaker ends up dealing with a bunch common criminals from 1800s London, not only will they have little motivation to speak in a way that is easier to understand, but they might deliberately overuse their slang so that the time traveler is revealed as someone "not from this part of town".
• The education level and social class of either party. Obviously a professor of English literature will have more luck, but depending on time or place, the upper or lower classes may have a particularly confusing manner of speech.

Once again, recall that our 30 year old Englishman (let's call him Bob) could find himself in many conversations today where he would have no idea what's going on: Technical discussions between professionals, criminal slangs, various dialects and so on. But while it would be difficult for Bob to conceal that he's an outsider, if the other person is helpful it should be rare that they can't find a way to communicate (eg. speaking more clearly, slowly, without slang or in a more neutral accent).

Mid-20th century onwards

Up to roughly the 50s-60s, this situation remains the same. From various recordings, film, documentaries and other such primary sources, it seems like mainstream English underwent little substantial change. The accents may be a bit different, obnoxious teenagers may say "groovy" instead of "epic", but they pretty much talk in the same way. Possibly this has to do with the spread of TV, which established a sort of "common denominator" way of speaking for most of the anglosphere. After being amused by the trivial differences for a few weeks, Bob would get used to it and communicate without difficulty, and after a few months he could probably easily "pass" for a non-time traveler.

Early 1900s

WW1-WW2 seems like a period when spoken English begins to differ perceptibly. TV had not yet began to dominate culture, so regional and subculture-specific idiosyncrasies were common.

In video, audio, and books written in an "everyday" language (either for effect or because the author was uneducated) begin to sound "quaint", and often feature expressions that seem confusing. Bob would be able to communicate with most people from Day 1, but he would frequently be confused about this or that subtlety of meaning. It would be a while before he doesn't have to say "Sorry but what do you mean by..." about commonplace words and expressions multiple times per conversation. It would be a long time before he can learn to "pass".

Written English would be much easier, as evidenced by books, pamphlets and signs from this period, except for the occasional euphemism-du-jour which has since fallen out of fashion.

The two world wars are handy delimiters, but I would say that this period was only really succeeded in the 50s (and maybe even 60s), and the preceding period ended several years before WW1 began.

19th century

From roughly the first third (give or take 50 years, depending on time, place and other factors) of the 19th century up to WW1, I think the non-trivial unintelligibility starts. Beyond just I got the gist of what you're saying but I'm not sure what exactly that remark meant, we are getting into frequent I have no idea what the hell you just said for at least the first few days, especially with less educated people from lower classes.

Texts from this time are basically intelligible to modern readers, but it is clear that a fair bit of unintelligibility is lost in transcription, if you will. For instance, consider novels which try to render authentic every day speech, such as some of my Mark Twain's works.

I'd conjecture that the period is associated with the Industrial Revolution, the dominance of the British Empire, and the advent of the Prussian education system (which is ubiquitous to this day).

Age of enlightenment(ish)

In early 1800s, 1700s, and maybe late 1600s we get written works (even on complex topics like philosophy, history, religion and science) that are pretty much intelligible, but sometimes effortful reading much helped by a good dictionary.

Bob could, at worst, carry around a pad and communicate by writing, assuming he can find someone literate: we are now just before public education becoming common, and coincidentally literacy rates are shockingly low.

Alternatively, he could attempt to speak like he would write, but there are still large differences in pronunciation, vocabulary and what is considered idiomatic. He would struggle to introduce himself to the first person he meets. If the person has some complex concerns (eg. a guardsman on the lookout for spies) I don't think he could resolve the situation diplomatically by the end of the day. If it's not weeks before he stops feeling like he doesn't even speak the same language, he should consider himself lucky.

It might be a year or more until Bob is "fluent", and 5-10 years before he can pass. Once this process is complete, if he returns to his own time, he will experience a similar culture shock for several months to a couple of years.

Middle ages

Early Modern English, from which our current language evolved, was prominent from 1400s to late 1600s. During this time, English went from its pre-15th century form, which is unintelligible to modern speakers, to what we have now. We conveniently have Shakespeare's works, among many others, to demonstrate the nature of EME: It is very obviously on the cusp of being an entirely foreign language in all but name.

Even written material is difficult to understand unabridged. An educated reader (even if the education includes reading Shakespeare!) can understand a fair bit of Shakespeare's works, but there will still be a fair bit which is hopelessly opaque: Too many words are simply not used anymore, or mean entirely different things. Without a glossary, it would be a tremendous effort to decipher them.

We have no way of knowing exactly how people spoke day to day around this time. However, it's likely very different. Unlike the period above, you now have a vicious circle sabotaging any efforts at communication: Ordinarily, you would segment speech into words and then try to figure out the unfamiliar ones, but the pronunciation is too unfamiliar for that. However, you can't figure out the pronunciation either, since you don't know what the words are and can't effectively look for them.

You are two thirds of the way to learning a whole different (but similar) language, like French. The vocabulary is different (even though a lot of words are the same, or at least about the same), the phonology is different, it's only the grammar that is mostly the same. How much does it take for Bob to become fluent in French? Let's say 6 years with instruction, well, call it 4 for EME. Of course, that is with instruction...

The key event here is probably the printing press, which began spreading around England in the 1400s. Note, also, that only towards the end of this period did English start to spreading to areas of the world (America) outside of Britain proper.

Early middle ages

We are now firmly on the other side of the hump and into "it might as well be a foreign country" area.

A good, familiar example of this is Chaucer's writing. Bob can't read it. He literally can't read the script. If it was put into a modern font (something impossible without professional help), he would not understand the words. If it was spoken it would sound like gibberish.

Considering the various social aspects of this period, I would seriously doubt Bob's long-term survival. He could easily get killed, imprisoned, or otherwise get into a lot of trouble due to inevitable misunderstandings and miscommunications.

If you have Bob ever managing to communicate with anyone, such as after years of trial and error, you have to invoke a stroke of luck soon after his arrival to this period or before, such as a kindly benefactor who supports him for many months when he is unable to function in society.

The key event is the Norman Invasion in 1066, which is when a bunch of Frenchmen invaded Britain, put themselves in charge, and didn't even bother speaking proper English.

The dark ages

Remember how I compared learning early English to learning French? If Bob arrives prior to the Norman Conquest, it might actually be harder. I would say that difficulty is comparable to learning a Nordic language, such as Norwegian, today. I doubt Bob would do any better than Hans or Xavier if he went this far back.

The key event here is the Roman conquest of Britain, and the spread of Christianity: Both provided a host of Latin words and influence, which produces a fair bit of common ground for modern speakers to discover.

However, if you go farther than that, just give up on having any intelligibility whatsoever. As far as 500 BC, I suspect it won't make much difference to Bob whether he arrives in the British Isles or China. Good luck, Bob! Wouldn't wanna be in your shoes!

NB: The periods I give above are very approximate. I tried to note what historical events strongly influence the change in language, but ultimately different parts of the world were undergoing the change at different rates, as were different strata of society.