Etymology

From OE herebeorg (fem.) ‘lodgings, quarters’ (cp. OHG her(e)berga, OS heriberga, MDu herberge ‘lodgings’ (all fem.) and OIcel herbergi (neut.) ‘inn; closet, room’), ultimately a compound of PGmc *xarjaz ‘army’ (OE here, OIcel herr etc.) + *ƀerʒō ‘protection’ or a related n. (OE beorg, OIcel bjǫrg etc.). The OE and ME nouns have sometimes been regarded as loan-translations from ON esp. by early studies (e.g. Skeat 1892, Kluge 1901: 933; then (tentatively) by OED  and de Vries), but the possibility of ON input is more often rejected as unnecessary (thus SPS, Dance 2003: 449) or omitted altogether (MED, Morris, TGD, GDS), and the ON n. itself has been regarded as a loan from LG (e.g. Mag.).

PGmc Ancestor

*xarjaz + *ƀerʒō 

Proposed ON Etymon (OIcel representative)

herbergi ‘inn; closet, room’, 
(ONP herbergi (sb.))

Other Scandinavian Reflexes

Far herbergi, Icel herbergi, Norw herbyrgi, Dan herberg(e), Sw härberge

OE Cognate

herebeorg ‘lodgings, quarters’ 

Phonological and morphological markers

Summary category

CCC4a

Attestation

Common and widespread in ME (also in place-names: see EPNE); on the late OE attestations see SPS.

Occurrences in the Gersum Corpus

Gaw 755, 812

Bibliography

MED herberwe (n.) , OED harbour, harbor (n.1) , HTOED , Dance herber (n.), SPS 446, de Vries herbergi, Mag. herbergi, Orel *xariz ~ *xarjaz; *ƀerʒō, Kroonen *harja-, AEW here; beorg (3), EPNE here-beorg