late 15c., herbengar "one sent ahead to arrange lodgings" (for a monarch, an army, etc.), alteration of Middle English herberger "provider of shelter, innkeeper" (late 12c.), from Old French herbergeor "one who offers lodging, innkeeper," agent noun from herbergier "provide lodging," from herber "lodging, shelter," from Frankish *heriberga "lodging, inn" (cognate with Old Saxon, Old High German heriberga "army shelter"), from Germanic compound *harja-bergaz "shelter, lodgings," which is also the source of harbor (n.). Sense of "forerunner, that which precedes and gives notice of the coming of another" is mid-16c. The unetymological -n- is from 15c. (see messenger). As a verb, from 1640s (harbinge "to lodge" is late 15c.).