Redolent comes from Latin redolent-, stem of redolēns, present participle of redolēre (to emit or give out a strong odor) - equivalent to red (back, again) + olēre (to smell) (akin to odor).  Possibly from old French to late Middle English.  

First recorded in late Middle English 1150–1500.  According to the Oxford English Dictionary, the first recorded use of "redolent" in English was in the Middle English period, with evidence of its usage before 1439, likely in the writings of poet John Lydgate; meaning the word was first used around the late 14th century or early 15th century. 

Examples of redolent in a sentence. 
The album is a heartfelt cry, redolent of a time before radio and television.
The mountain air was redolent with the scent of pine needles.