The earliest use of it in print that I can find is from The New Monthly Magazine and Literary Journal, 1833. It is from a "paper" titled "The Story of Hester Malpas," by L.E.L.:
Hester now looked at her aunt, who was the very reverse of what she had imagined : she had always thought she would be like her father, and fancied a tall, dark, and handsome face.
According to an excellent post found at Wordwizard.com, and as seen in the citation above, the phrase was originally used to describe women as well as men up until the early 20th century (see EL&U discussion herehere). Also of note, the popularity of the phrase spiked after a movie by the same name was made in 1941 starring Caesar Romero.