As far back as 1858 when the first Methodist service was held in Toowoomba a need was identified to establish a church in the region. This happened in the mid 1860s, when a small stone church was built in Neil Street, but not before long, due to the growing size of the congregation, a new church had to be built. As a result a new block of land was purchased not far from the original church for £550.00 in April 1976.
This new site located at 54 Neil Street, would become the location for the new Wesleyan Methodist Church. Designed by Queensland architect Willoughby Powell, the church has a Gothic architectural style and was built by R. Godsall. The founding stone was laid in August 1877. Construction cost £2300, and the building was complete by 1877. The stained glass used throughout the church was manufactured by Sydney firm Ashwin and Falconer.
A timber school room was added in 1882 by architect James Marks. Extensions to the church was made in 1901 and an iron gate and masonry fencing was added to the site in 1824.
By 1977 the Methodist, Presbyterian and Congregational Churches amalgamated and the Wesley Uniting Church was established. In 1997 the church building was connected the the Empire Theater with a glass walkway.