A former slave, Solomon Melvin Coles was born in Petersburg, Virginia. Before the Civil War, a sheriff disobeyed the law by teaching Coles to read. He worked his way through college beginning at Guilford Institute, Connecticut, as the first black student. He earned a bachelor's and a master's degree at Lincoln University, Pennsylvania, and a Bachelor of Divinity at Yale. He organized the Nazarene Congregational Church, First Black Congregationalist Church in Brooklyn, New York, before coming to Texas in 1877.
Ordained in Goliad, Texas, he began preaching in Corpus Christi and teaching black students who only attended school two months of the year. In 1878, believing education essential to black children, Coles gave up the ministry to teach and serve as principal at the school in the 500 block of North Carancahua. The school moved in 1893 to this site and was known as the Public Free School for Colored. The existing building was a converted broom factory. The following year Coles moved to San Antonio where he taught until his retirement in 1914. In 1925 this structure which served as a high school was built and named for Coles. In 1973 it became Solomon M. Coles Elementary School.