A graduate of Yale College and Princeton Theological Seminary, Cleveland spent most of his life as a pastor, outside of a brief period as a district secretary for the American Home Missionary Society.

Described as a "thin, pale, and intelligent boy" by Allan Nevins, he worked for periods at an uncle's cotton mill and as a store clerk before winning acceptance into Yale College.

He graduated summa cum laude in 1824, and almost immediately moved to Baltimore, Maryland, where he began working as a teacher in a private school.

His tenure there was not overly successful – the parishioners chided his wife for her colorful clothing and jewelry and were scornful of their decision to bring an African-American woman with them from Maryland as a maid.

He enjoyed the position, but the frequent travel over poorly-maintained roads took a toll on his health, aggravating a gastric ulcer that he had developed.

[3] Cleveland sought a return to the easier life of a pastor, and in September 1853 found an appointment at a Presbyterian church in Holland Patent, New York.