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, travellers were often given board and lodging by locals, especially those higher up the social hierachy. After 1300, though, there are an increasing number of references to inns and hostels as well ...
Some of the early lines of Chaucer's prologue to The Canterbury Tales (circa 1386), tell of The Tabard inn in Southwark, just south of London Bridge.
In Southwerk at the Tabard as I lay
Redy to wenden on my pilgrymage
To Caunterbury with ful devout corage,
At nyght was come into that hostelrye
Wel nyne and twenty in a compaignye
Of sondry folk, ...
So far all the links I've found about this hotel and Columbus start with "legend has it" or "they say". While Columbus stayed in Cordoba for some time, while trying to woo the spanish monarchs to fund his expedition, he was staying at the "Convento de la Merced" (Mercy's convent) (link in spanish). Then he returned briefly to Portugal, and when he came back ...