Old English wilcuma "welcome!" exclamation of kindly greeting, from earlier wilcuma (n.) "welcome guest," literally "one whose coming suits another's will or wish," from willa "pleasure, desire, choice" (see will (n.)) + cuma "guest," related to cuman "to come," from PIE root *gwa- "to go, come." Similar formation in Old High German willicomo, Middle Dutch wellecome.
Meaning "entertainment or public reception as a greeting" is recorded from 1530. The adjective is from Old English wilcuma. You're welcome as a formulaic response to thank you is attested from 1907. Welcome mat is from 1908; welcome wagon is attested from 1940.