Yes, there were, but information on inns and hostels before around 1300 is patchy at best and the evidence suggests that, for the early middle ages especially, travellers were often given board and lodging by locals, especially those higher up the social hierachyhierarchy. After 1300, though, there are an increasing number of references to inns and hostels as well as some physical evidence.
DETAILED ANSWER (this is mostly, but not entirely, chronological and refers to England unless otherwise stated)
Evidence of inns or hostels in Anglo-Saxon England and among the Norsemen is limited. In part, this may be because there were few of them as there was little need in many places (see below, although it is hard to imagine that there weren't any inns or hostels in major urban areas such as London, Paris and Rome). There were fewer travellers than in later times and the custom in Scandinavian and Anglo-Saxon societies was to provide food and lodging for travellers. In Icelandic society at least,
Although one might expect enterprising individuals to set up inns in areas where there was a demand, this does not appear to have always been the case. In early 12th century Norway, King Eystein I (reigned 1103 to 1123) set up a hostel in Dovreset up a hostel in Dovre because,
As visitors such as craftspeople and merchants came in increasing numbers to BergenBergen, the traditional hospitality that travellers could normally expect would no longer suffice
A statute of King Edward I of England in 1285 mentions the ownership by foreigners of, among other things, hostels and inns; later, foreigners were barred from owning such establishments along the River Thames in London.
According to John Hare in his book Inns, innkeepers and the society of later medieval England, 1350–1600, inns "were a crucial part of the economic infrastructure of the country". Also, Phillipp R. SchofieldPhillipp R. Schofield, in Peasant and Community in Medieval England, 1200–1500, states
As inns became more common in the 14th century, they began to put up signs (with pictures, for many people were illiterate) as a way of advertising themselves. By the time of Chaucer Chaucer (at leastdied 1400) at least, one could find a wide range people when one walked into an inn or tavern. In addition to adventurers, among them were
Also in France, another example of a hostel was at Cluny monastryCluny monastery:
Source: J.L. Singman, Daily Life in Medieval Europe'Daily Life in Medieval Europe' (1999)
In England, The Angel Inn in Andover (Hampshire, southern England) has been in operation since at least 1456 in the current building (built between 1444 and 1455, although the facadefaçade is much more recent). Another example is The New Inn in Gloucester, built in 1450.
A 1973 photograph of The New Inn, Gloucester—the most complete surviving example in Britain of a medieval courtyard inn. Attrib: Alan Longbottom [CC BY-SA 2.0 (https://creativecommons.org/licenses/by-sa/2.0)], via Wikimedia CommonsAttrib: Alan Longbottom [CC BY-SA 2.0 (https://creativecommons.org/licenses/by-sa/2.0)], via Wikimedia Commons
Source: D. Webb, Pilgrims and Pilgrimage in the Medieval West'Pilgrims and Pilgrimage in the Medieval West' (2001)
G. J. White, The Medieval English Landscape, 1000–1540'The Medieval English Landscape, 1000–1540' (2012)