early 14c., "narrative dealing with a happening or an event," from Old French legende (12c., Modern French légende) and directly from Medieval Latin legenda "legend, story," especially lives of saints, which were formerly read at matins and in refectories of religious houses, literally "(things) to be read," on certain days in church, etc., from Latin legendus, neuter plural gerundive of legere "to read; to gather, pluck, select," from PIE root *leg- (1) "to collect, gather," with derivatives meaning "to speak (to 'pick out words')."
Extended sense of "nonhistorical or mythical story," with or without saints, wonders, and miracles is first recorded late 14c. Meaning "writing or inscription" (especially on a coin or medal) is from 1610s; on a map, illustration, etc., from 1903. To be a legend in (one's) own time is from 1958.