The site was originally occupied by a mission church completed in June 1939 and called St Francis’. In 1949 a scheme was proposed to build a new church eventually called St Matthew on the Hill. In 1955 it was called St Francis' Church Hall.
The church of St Mathew on the Hill was completed in 1959 in the middle of the Bestwood Estate on Padstow Road and was opened on 10 October that year. It was designed by the Nottingham architect Vernon Royle. The foundation stone was laid in 1958 and was the stone from St Matthew's Church on Talbot Street (demolished 1956).
When Royle submitted plans for St. Matthew’s church, Bestwood, with felt covering to the roof (as he had only £8,000 budget to spend) approval was only granted on condition that a promise was given to replace the felt with copper as soon as funds could be made available. Pews from the Victorian church of St Matthew, Nottingham were re-used; they were made of pitch pine, stained and varnished. Royle had them painted in three colours arranged alternately, and also used the font and the eagle lectern from the old St. Matthew's. He said that he managed to build a 'well-insulated barn of a church' 90ft x 70ft x 30ft high for just £8,000 based on the design of three churches built in the Coventry Diocese by Basil Spence.
Royle had one regret he admitted to in his post-war Nottinghamshire churches, which was the tower of St. Matthew’s Church, Bestwood. He stated that his original design would have cost £6,000 and was not built due to financial restraints. The much cheaper tower erected is not one he was proud of.
Since 1959 St Matthew’s has worked to support the community in both their spiritual and secular lives. In the 1980s, it opened its doors to offer assistance and advice on legal and welfare rights to local unemployed people.
In 2009 the church was badly damaged in an arson attack. The loss caused by the fire was valued at £300,000.
Despite this incident, the congregation still gathered to celebrate the church’s 50th birthday in October 2009 with an open-air party. A marquee was donated for the purpose.
Since the fire, the congregation have been worshipping in the sister church of St Philip’s in Top Valley.
In 2009, vicar Andy Morris and his wife expressed their hope that, should the church be demolished, a new one might be built somewhere between Top Valley and the Bestwood Estate, merging St Matthew’s with St Philip’s.
The church was demolished on 3 May 2019.