In earlier times a church festival or saint's day; more recently, any special day.
This comes from the practise of marking the dates of church festivals on calendars in red.
The first explicit reference to the term in print that we have comes from America. This is a simple use of the term "Red letter day" in the diary of Sarah Knight - The journals of Madam Knight, and Rev. Mr. Buckingham ... written in 1704 & 1710, which was published in American Speech in 1940.
The practice is much earlier than that though. William Caxton, referred to it in The boke of Eneydos, translated and printed in 1490:
The term came into wider use in 1549 when the first Book of Common Prayer included a calendar with holy days marked in red ink. For example, Annunciation (Lady Day), 25th March, was designated in the book as a red-letter day."We wryte yet in oure kalenders the hyghe festes wyth rede lettres of coloure of purpre."
The term is sometimes written without the hyphen - 'red letter day'.