early 14c., from Old French forteresse, forterece "strong place, fortification" (12c.), variant of fortelesse, from Medieval Latin fortalitia, from Latin fortis "strong" (see fort) + -itia, added to adjectives to form nouns of quality or condition. French -ess from Latin -itia also is in duress, largesse, riches, also obsolete rudesse, "lack of cultivation" (early 15c.).
For change of medial -l- to -r- in Old French, compare orme "elm" from Latin ulmus; chartre from cartula; chapitre from capitulum.