The Pentecostal movement in the Lee County area began in the summer of 1917 when E.L. Partee from Pontotoc County invited Rev. J.R. Higgingotham from Arkansas for a revival meeting. The Pontotoc people who had embraced the Pentecostal faith came to Lee County to attend the funeral of Mr. J.R. Montgomery in the Union Community, and while there held a prayer meeting. This prayer meeting was the source of the organized Pentecostal Church in Lee County and eventually at Nettleton.
The believers moved from the Union Community and began services in the Eureka Community, East of Nettleton. In January of 1937 the land on Maple Street was leased for twenty years and the first church building, a frame structure, was constructed. In August of 1937, the church building burned, apparently from arson. Construction of a new church building began immediately. The new church was constructed with living quarters in back and someone resided in the building for a number of years to prevent another church arson. In 1949, the church members purchased the plot of land they had leased, and in the 1950's, the brick church building was constructed. In 1960 a large educational annex was constructed. Ten years later, another annex was constructed to house additional classrooms, a baptistry, dressing rooms, and an enlarged choir loft. In 1978, the sanctuary was renovated to add a balcony and a thirty foot addition to the front was added to enlarge the auditorium, add restrooms, and a large foyer. Additional Sunday School classes were added on each side.