1580s, "structure affording protection," possibly an alteration of Middle English sheltron, sheldtrume "roof or wall formed by locked shields," from Old English scyldtruma, from scield "shield" (see shield (n.)) + truma "troop," related to Old English trum "firm, strong" (see trim).
If so, the original notion is of a compact body of men protected by interlocking shields. OED finds this "untenable" and proposed derivation from shield + -ture. Figurative sense is recorded from 1580s; meaning "temporary lodging for homeless poor" is first recorded 1890 in Salvation Army jargon; sense of "temporary home for animals" is from 1971. Related: Shelterless.