late 15c., "ornamented with scenes from history" (of books, walls, etc.), from past participle of verb form of story (n.1). Meaning "celebrated in history or legend" is from 1725.
storied (adj.2)
"having stories or floors" of a certain type or number, 1620s, from story (n.2).
store
storefront
storehouse
storekeeper
store-room
storied
stork
storm
storm-trooper
stormy
story