Born in Petersburg, Virginia in 1844, Solomon Melvin Coles had been enslaved by the Pryor family of Dinwiddie County, Virginia. Before the Civil War broke out, he was tutored in the home of H.J. Heartwell, the county sheriff. Following the war, he worked in Norfolk, Virginia and saved money to travel north to continue his education. In 1866, he became the first Black student to attend the Guilford Institute, a Congregational school. In 1869, he entered Lincoln University as a sophomore, earning his BA in 1872 and his MA in 1874. The first recipient of the scholarship established through Mary A. Goodman’s bequest, Coles attended Yale Divinity School from 1872 to 1875 and was the first Black student to enroll at the Divinity School. He graduated from Yale in 1875.
Coles was sent by the American Missionary Association to Charleston, South Carolina, but before he went he was called to Brooklyn to help organize the Nazarene Congregational Church (the first Black Congregational church in Brooklyn). Ordained in 1877, Coles became pastor of the Freedom Congregational Church in Corpus Christi, Texas, and was the teacher and principal of the Colored Free School. In 1883, he helped establish the Colored Teachers State Association of Texas and served as its first president. Coles remained in Corpus Christi until 1894.
In 1887, Coles married M. Cornelia Lewis in New Orleans. They had two children. His wife and one of his daughters died in 1891.
In 1894, Coles relocated to San Antonio, where he taught English, math, and Latin at Riverside Elementary and then at Douglass Elementary for 20 years.
In 1914, Coles retired and lived with his daughter in Oberlin, Ohio, until his death in 1924.