Origins
Before shelter meant a roof over your head, it may have meant a wall of shields at your back. The word probably descends from Old English scildtruma — scild ('shield') plus truma ('troop') — a military formation in which soldiers locked their shields together to form a protective barrier.
The Middle English form sheltron named a specific battlefield unit: a dense rectangular block of infantry, shields overlapping, bristling with spears. At Bannockburn in 1314, Scottish sheltrons held firm against English cavalry charges. The formation was the shelter.
The civilian meaning emerged in the 1580s, transferring the image from battlefield to daily life. A shelter was anything that shielded you — from rain, from wind, from danger. The military precision fell away; the sense of protection remained.
Later History
The etymology is disputed. Some linguists propose Middle Dutch schulder ('to take shelter') as the source instead. But the shield connection is widely favoured, and the semantic journey from shield-wall to bus shelter has a satisfying logic: both are barriers between a person and an incoming threat.
Modern English has extended shelter into finance — a tax shelter shields income from taxation. The word's journey from Anglo-Saxon battlefields to accountancy offices spans a thousand years.