Having bought land here in 1842, the Rev. M. P. Meyers moved to Byhalia in 1843. The Native Americans had already named the town after the huge white oak trees which abound in the area.
The Rev. Myers and others began constructing a crude log meeting house, located on the present cemetery grounds. Br. Myers preached in this two room building. On week days, the building served as a school.
In 1855-56 a two-story frame building was erected on the site of the present church. The Masonic Lodge met in the upper story. The land for the building was provided by Mr. F. W. Henry and Mr. D. W. Sharp laid the cornerstone, which records the date, Oct. 11, 1956.
The church was in the Memphis Conference until the organization of the North Mississippi Conference at Water Valley in 1870. It has changed several times back and forth between the Holly Springs and the Sardis Districts and is now in the Senatobia District.
About 1884 a Ladies Aid Society was organized and funds for the first parsonage were started. Rev. J. T. Moody was the first pastor to live in this parsonage, the first to be owned by the church.
In 1906 a new brick church building was built under the guidence of Pastor S. A. Brown. The Building Committie was composed of W. C. McCrary, J. L. Burrow, E. B. Horn, S. C. Mims, D. W. Sharp, and W. D. Fitts.
In the 1920's there was a period of expansion. A Sunday School annex was built in 1928 and the present brick parsonage was completed in 1931. Rev. J. D. Simpson and his family were the first to occupy it.
A new Education Annex was dedicated by Bishop Marvin A. Franklin on Mar. 1, 1959. The dedication program was followed by a reception in the Fellowship Hall.
After an unsuccessful attempt several years earlier, Byhalia became a full time church. Prior to this time, the paster had served three churches: Byhalia, Emory, and Fountain Head.
On April 23, 1968, in Dallas, Texas, the Methodist Church merged with the Evangelical United Bretheren, a church of similar historical and spiritual heritage and doctrin, whose origin can be traced back to John Wesley, to form the United Methodist Church.
Byhalia United Methodist Church was entered on the National Register of Historic Places in May 1984 and welcomed its first lady pastor, Rev. Ruth Mayhew Wood in June of the same year.
The people of Byhalia United Methodist have always supported the activities of the area and the church has been the meeting place for many of these activities. The United Methodist women have played a very vital part in the church all through the years and their organization has been deeply interwoven in the church's history
Byhalia United Methodist Church continues to reach out in love and service to the community and the world, in an attempt to bring others into a saving knowledge of Jesus Christ.
Byhalia U M C once again became a "station" church in June,1995 after having been a part of a two-point charge with Barton U M C.
The 1996 Mississippi Aunual Conference underwent a re-districting program with Byhalia U M C remaining in the Senatobia District.