In Middle English, the word welcome went through many alterations, taking unrecognizable forms such as wolcume, wulcume, wilcume, and wilcuma. All, however, carried the same definition and all trace to the Old English term wilcuma, a noun literally meaning "one who arrives at the pleasure of another". This is a combination of willa, or "pleasure", and cuman, or "to come" (yes, the word come comes from this, through a couple more similar spellings in Middle English as well). Willa, through Proto-Germanic wiljana, goes back to Proto-Indo-European welh, or "to wish". Another interesting part of willa is that while it is related to our word well, it's closer so to will, and the modern modification that looks like well in welcome is actually an instance of folk etymology; people thought that that was supposed to be the correct spelling, and changed it to be so. Instead of hoping someone comes well, the word wills them to come, but that's largely forgotten today. Meanwhile, cuman, through Proto-Germanic kwemana, traces to PIE gwem, which meant "to step". You can see the "traveling" semantic connection. So, welcome etymologically means "wish step", because it bids people to come forward. So how did this get adopted in you're welcome? When you reply with that nicety, instead of inviting them to come, the meaning shifted to inviting them to ask for such a favor again. Today we don't even consider it. Well, we'll come around.
Adam Aleksic, a rising sophomore studying linguistics and government at Harvard University, has been described as the internet's sixth most famous etymologist. He also has disturbing interests in politics, vexillology, geography, board games, conlanging, and law.