"rarely, not often, infrequently," late Old English and early Middle English seldum, an alteration of seldan "infrequently, rarely," from Proto-Germanic *selda- "strange, rare" (source also of Old Norse sjaldan, Old Frisian selden, Dutch zelden, Old High German seltan, German selten), a word of uncertain etymology. Perhaps ultimately from the base of self (q.v.).
The form shifted apparently on analogy of adverbial dative plurals in -um (as in whilom "at one time," from Old English hwilum, from the source of while). The same development also created litlum from little, miclum from mickle. Also compare random, ransom. The forms in -n decreased from 14c. and faded out in 16c.
Old English seldan had comparative seldor, superlative seldost; in early Middle English, as seldan changed form and lost its connection with these, selde was back-formed as a positive. Shakespeare uses seld-shown "rarely exhibited." Some compounds using the old form survived through Middle English, such as selcouth "rarely or little-known, unusual, strange, wonderful," from Old English selcuð, seld-cuð, from seldan + cuð (see couth).
German seltsam "strange, odd," Dutch zeldzaam are cognates of seldom, but with the second element conformed to their cognates of -some. Related: Seldomness.
Seldom-times "rarely, hardly ever" is from mid-15c. (earlier was seld-when, Old English seldhwanne "rarely," which lasted until 16c.). Seldom-seen "rarely encountered" is from mid-15c.; older was seld-seen (Middle English seld-sen, from Old English seldsiene), which lasted long enough to appear in Marlowe (seildsene, 1590s).