The earliest existing historical records of the church date back to the year 1354, but the church was not built that year. The first church in Melum was a wooden stave church that may have been built during the 13th century. That building was dedicated to St. Laurentius. In 1723, the church was sold into private ownership during the Norwegian church sale when the King sold the churches to pay off debts from the Great Northern War. This church, along with 13 other local churches, were purchased by the provost Peder Alstrup of the local Bamble prosti. At that time, the old church was in poor condition, so it was not long before the new owner decided to tear down the old building and replace it with a new church on the same site.[3][4]
The new building was a wooden long church with a choir on the east end of the nave. The new church was consecrated on 24 October 1728. In 1737, Alstrup sold the church to Captain Christian von Barnholdt. In 1767, a tower was built on the church. In 1828, the Løvenskiold family purchased the church. In 1840, the old tower was removed and a new, larger tower was built on the west end of the nave. A church porch is located beneath the tower and that is used as the main entrance to the church. In 1854, the local municipality took ownership of the church which had been privately owned since 1723. In 1883, the pews were changed, and the church got new windows and a new baptismal sacristy. In 1897, the interior walls were paneled to cover up the log construction and the ceiling was changed. In 1970–1976 the interior was restored and the wall paneling was removed.[4]