Mellville House was built in 1697 by the architect James Smith (c. 1645–1731) for George Melville, 1st Earl of Melville (1636–1707). The remains of the 14th-century Monimail Palace which the Melvilles had bought in 1592 were incorporated into the grounds as a folly. The estate once bordered the nearby royal estate of Falkland Palace which had been a popular retreat with all the Stuart monarchs who used the vast surrounding forests for hawking and hunting deer. Wild boar, was also imported from France and hunted in the area.^[2] Melville however was to be accused of being involved in the Rye House Plot — a Whig conspiracy to assassinate King Charles II and his brother the Duke of York (the future James VII). To escape arrest Melville fled to Holland where he joined the band of British Protestant exiles at the court of Prince William of Orange. Here Melville became one of the chief Scots supporters of William of Orange.^[3]

During the 1940s, the estate and house was used to billet Polish soldiers during World War II who were training for a guerilla campaign against any German invasion throughout the Blitz period. Scotland was seen as a prime target for an invasion by the Nazis via their bases in Norway, throughout 1940–1942^[4] After the war the estate was purchased by Dalhousie Preparatory Boarding School, when they moved premises from Dalhousie Castle in Lothian. It remained a private preparatory school from 1950 to 1971. During the 1960s in non-school termtime weeks Outward Bound utilised the school by hiring it as a Scottish residential centre for their worldwide and challenging outdoor adventure programs. Later Melville House became a special education boarding school from 1975 to 1998 with fees varying from pupil to pupil.^[5] In general, the education department would consider referrals of unique boys who displayed both academic potential and/or difficulty developing within mainstream education, and in several cases funded the fees. However, in other cases, some guardians were required to contribute toward said fees after completion of a financial assessment.

In 1976, a new standardised modular design system building was erected at considerable expense upon the old walled fruit garden. This was a one level permanent core building containing an indoor football area and gymnasium, an administration area, showers, locker rooms, library and a limited number of permanent classrooms in science, mathematics and computers.^[6] Finally, in 1977, the board developed the former stables building into a history classroom whilst additionally creating, in the upper section, accommodation for a senior house master and his family to occupy.

Novelist Lady Mary Hamilton, daughter of Alexander Leslie, 5th Earl of Leven, was born here in 1736.^[7] Former Lord Provost of Edinburgh, Francis Brown Douglas, died here on 8 August 1885.^[8] Journalist and former editor of The Scotsman newspaper (1985-1988), Chris Baur, whose BBC2 television programme Power of Scotland won the Royal Television Society's Journalism Award for the best current affairs documentary of 1978, was a pupil.^[9] The Scottish historian and novelist Mauro Martone, is presumed to have been a pupil and briefly mentions the estate in his 2017 novel "Kertamen".^[10]

In the early 2000s, the house was refurbished as a private home, before then being sold on several years later. After the purchaser failed to sell the property for a £4.5m asking price, Melville House was repossessed by the South African bank which had lent the money, making it the most expensive repossessed property in Britain.^[11]

Melville House is a category A listed building,^[12] and the grounds are included on the Inventory of Gardens and Designed Landscapes in Scotland.^[13] The Melville State Bed, made in 1700 for the Earl of Melville, was given to the Victoria and Albert Museum in London in 1949 where it is described as "the most spectacular single exhibit in the Victoria and Albert Museum's British Galleries".^[14]