In short, no, there was nothing like the thousands of miles of 'wilds' in Europe like there are in Tolkein's Middle Earth - even in the far north and east the landscapes were inhabited and carefully managed by nomadic and pastoral communities. That's not to say that there was no wilderness at all in the middle ages, but it's fairly uncontroversial to say that there wasn't a huge amount more than there is today (certainly by the end of the medieval period).

The European landscape at the beginning of the middle ages - which was inherited from Iron ages and classical societies - was certainly covered in more trees than we see in Europe now - but it's a misconception to call this woodland 'wilderness'. These were woods which were heavily and deliberately managed by local rural communities as precious resources. Woodland provided timber for building and firewood, pasture for pigs and other animals and seasonal opportunities to supplement diets with game and foraged herbs, berries and fungi. As a result, access rights to woodlands were fiercely guarded and policed throughout the middle ages, and are probably the single most common example of rural class conflict in before 1000. Europe was covered in trees, but we shouldn't picture a dense ocean of forest stretching for mile upon miles, but an interconnected series of smaller human-managed woodlands interspersed with settlements and other types of landscape. (Obviously this description, like most of the others that will feature in this post, is a huge generalisation; Europe is a big continent and local landscapes and ecologies varied enormously from region to region.)

This picture of Europe beings to change with Europe's great demographic boom which kicks off in the years after 900. An increased population, coupled with changing socio-economic factors lead to an increased demand of cereal-grains and arable agriculture, at the expense of the older, less-intensive methods of mixed agriculture. Much of the previously carefully-managed woodland was ripped up (rather than cut down - an incredibly labour-intensive process made necessary by the fact that you can't plow a field full of roots) and replaced with cereal mono-cultures, while pastoral and mixed agriculture retreated to those areas that couldn't sustain the intensive arable farming. This large-scale transformation of the landscape reached its peak in the twelfth and early-thirteenth centuries, as people migrated further and further - east into Slavic territories, west into Wales, Scotland and Ireland and south into Muslim Iberia - clearing more and more land to support them. While much of the focus has been on clearing woodland in this answer, draining marshes and bogland, diverting rivers and a host of other man-made interventions were part of this massive drive of agricultural intensification across Europe. It's been estimated that between half and two-thirds of the woodland cover of the early middle ages was removed as part of this process; England, by Domesday book's record in 1086, was already only 15% woodland.

The result of this intensification was that remaining non-cultivated or partially-cultivated areas were managed even more carefully and guarded ever-more jealously. Every possible natural resource - from woodland to rivers, quarries to pasture, salt flats to oyster beds - was exploited and managed to best suit its owners and they remained vital to local communities. By the end of the middle ages, the landscape was very similar to that we see today in most parts of Europe, dominated by small villages and farmland, interspersed with patches of woodland, marshes and other 'wilder' areas - but it's very difficult to describe any of it as 'the wilds' in a Tolkeinesque sense.

People in this thread have been saying "the Middle Ages is tough to generalize because it encompasses so much territory and time"--and then going ahead and smoothing out the interesting texture in favor of telling a sweeping, monolithic story. This isn't bad-it can actually be really helpful--but medievalists also like complication. ;) So let's talk about the interesting texture, too!

First, it's absolutely true that from even the end of the first millennium, Europeans were embarking on massive amounts of land clearance and drainage for agriculture and pastoralism (livestock grazing). Although scholars used to think a lot of this happened in the twelfth and thirteenth centuries, archaeological and linguistic (place names) evidence now points to a much earlier date. This rural development leads to and coincides with population growth. Earlier, according to David Herlihy in Medieval Households, medieval settlement patterns in northwest and central Europe did tend to be a cluster of habitations and farmland around a local core, rather than being evenly distributed.

But note there I said northwest and central Europe--France, Germany, England, the Low Countries. Because the standout here is the Iberian peninsula.

When you look at maps of the Muslim conquest of Spain, the solid color splotch takes up most of the peninsula, with just a crescent of Christian territory temaining in the north. These maps reflect settlement patterns of the Christian kingdoms, not the Cordoba caliphate. In fact, while I we shouldn't talk about the interior as "empty", Islamic Iberian civilization was very, very heavily bunched on and near the coast and some interior waterways.

Thus, the Christian "Reconquista" from the eleventh century involved a lot more claiming land than claiming land from Muslims. In fact, a major problem new Christian territorial lords had was getting enough people to hold their land for themselves! That's why Spain is the place in the West where Jews can and do systematically, legally own and sometimes work land. Christians actually recruited them to move north from the al-Andalus cities and villages to oversee proper development of arid land into irrigated, arable farmfields and sufficient pasture. And pastoralism entrenched itself as a major economic focus, rather than cultivated land in a lot of places.

In mainland Europe, so, you'd have a castle and a town either springing up around it or that it was built to protect, and its walls would encompass part of the town and a few fields/orchards. In Spain, a castle might be one corner of a large network of walls protecting villages and grazing land up to 24 hour walk. Then, to guard the walls, additional isolated castles might be built. So the Spanish heartland might not have stayed empty, but it was certainly a lonelier and more wild-looking place.

Secondly, there is the phenomenon of natural reclamation. One thing people tend to miss is that Europe's massive high medieval population boom didn't last. In Italy, in fact, population decrease (not just slowdown in increase) is already visible in some areas in the late thirteenth century. Over the early fourteenth century, it expands--and then of course the Black Death and subsequent waves of pestilence utterly devastate European populations. Chroniclers report entire villages and estates/manors of multiple villages simply wiped out altogether. Paleoarxhaeologically speaking, there is indeed reforestation. Because--crucially--there's no rebound! Europe's population stays lower for more than a century after the initial Black Death. Not until the 16th century is there really marked recovery. While I'm not sure abandoned villages and reforestation over 150 years would have the same "wilderness" feeling of driving through the American Rockies today, or wandering the Sahara, it was definitely a different landscape and a different human geography in 1400 than 1300.

But one final point I want to make: all of this is in a sense beside the point in this particular question. Because Tolkien wasn't rewriting medieval history, he was rewriting medieval literature. And in the medieval literary imagination, the dark depths of wild Europe permeated their understanding of an enchanted, holy world.

In Christianity, there's this idea of "the desert"--the earliest hermits, who would become famous as the first monks, are said to have fled society to live in isolated cells in the Egyptian desert. There they prayed, fought demons, and drew ever closer to God. Now, the irony here is that they were actually living prety much on the outskirts of town in reality. In legend, though, the imagined terrain of physical wilderness reflecting a spiritual proving grounds was their real home.

Western medieval Christianity drew heavily on this strong ascetic, self-denying, self-negating core tradition from the Desert Fathers. In western spiritual writing, "the forest" becomes synonymous with "the desert." That's why Arthurian knights are always getting advice from hermits in the forest. (In reality, anchorites were great advice givers, but they lived either in close proximity to towns or smack in their middle). It's a conceptual, imagined wilderness. Notably for present purposes, Spain is talked about as the desert in Christian writing! (Islamic sources actually tend to stress its fertile abundance and civilized societies...)

Tolkien's Middle Ages are the literary Middle Ages, the legendary ones, with pockets of happy hobbit civilization tucked into expanses of wilderness that serve as the space to prove one's worth again and again in the face of evil.