Constructed in 1867, First United Methodist Church is one of the oldest structures in Cattlesburg. The congregation was first introduced to the community of Catlettsburg as the Methodist Episcopal Church, South in the years prior to the Civil War. The early movement of Methodism in Boyd County was conducted at this time by traveling ministers on horseback. After the Great Revival led to a surge in interest throughout states such as Kentucky, membership within Methodist congregations increased and Methodism became the largest denomination in many southern and western communities in the 1830s. During the 1844 General Conference, where the debate over whether bishops could own slaves caused a split in the church, the Methodist Episcopal Church, South was created. Like many other churches in Kentucky and the South, this congregation dates back to this branch of the Methodist Church.
The early 1800s saw the spread of Methodism into Kentucky, and Boyd Country was no exception thanks to traveling ministers. John W. McReynolds traveled throughout Boyd County on horseback leading to the creation of small groups of Methodists that later formed the basis of many congregations that continue to this day. Similar to the Baptists and other leading Protestant denominations, the leaders of the Methodist Church avoided the issue of slavery. During the Conference of 1844, however, the Church split because they were unable to reach an agreement as to the propriety of bishops owning slaves. The split led to the creation of the Methodist Episcopal Church, South. The congregation was racially segregated until 1968.