The history of Melville Castle goes back to at least 1155 when Malleville was an estate owned by an Anglo-Norman baron named Galfrid de Malleville. The castle passed through marriage to Sir John Ross of Halkhead in the late 14th century. It remained in the Ross family until 1762 when it was bought by Sir David Rennie.

When Rennie died, the castle passed to his daughter, Elizabeth, who in 1765 married Henry Dundas (later created the first Viscount Melville). In 1786 Dundas had the medieval tower house demolished and commissioned James Playfair to build a modern three storey replacement, which was completed in 1791. Part of the original castle was incorporated into one of the wings of the new castle.

The castle remained in the Dundas family until it was sold in 1970 to Lt. H.L. Weibye, who ran it as a hotel. In 1988 it was sold again, but the castle was stripped and neglected, and soon became derelict. The castle was rescued by the Hay Trust, who bought it in 1993 and spent 8 years restoring it. During the renovation work the foundations of the old castle were discovered, as were a set of stone steps leading down under the main hall.

Re-opened as a 4 star hotel in June 2003, it closed for refurbishment in 2011 and opened again in March 2012 as wedding venue and private use castle.