The first surviving estate plan was drawn in 1797 by George Brown. The park was planted up during the early 19th century and further additions were made in the early 20th century by Charles Leith-Hay to his own designs.
The Leith Clan was settled in Aberdeenshire by the reign of Alexander III. The Leith- Hay family of Leith Hall are directly descended from William Leith of Barnes, Provost of Aberdeen in the reign of David Bruce, and Steward of the royal household of Queen Joan. He went to London as a hostage in 1346 after David II was captured in battle. Leith Hall was started in c.1650 by James Leith, the 13th laird, on the site of a former house known as Peill Castle.
The 13th Laird built the present north wing and was succeeded by his son John who died in 1727. Roy's map of 1750 shows only two enclosures at Leith Hall; one around the house and one to the north-east planted as woodland. John's grandson married Harriet Stewart of Auchluncart and additions were made to the house in 1756 in the form of a low, one-storey building around a central courtyard with pavilions at each corner. They had three sons; the eldest having died young, the second son, Alexander, succeeded as 16th laird in 1776, and in 1796 the south wing was built up to form the central south section of the present house, with Regency style features. George Brown drew up plans of the estate which indicated a kitchen garden to the north of the present garden. Other 18th century plans show formal gardens around the house and up to the stables which are shown with a complimentary mirror-image building to the east of the drive. It is not known whether the gardens were ever implemented but the east half of the stables was not.
Alexander had a distinguished military career becoming a General in 1813. His younger brother James also had a successful career, becoming Governor of Barbados where he died in 1816; he is buried in Westminster Abbey. The General also built the model Home Farm in the early 19th century to the north of the earlier semi-circular court of offices, and he extended the east front of Leith Hall House. The General died in 1838 when he was succeeded by his son Sir Andrew Hay of Rannes and Leith Hall, MP for Elgin from 1833-8 and a member of Lord Melbourne's administration. He also had a distinguished military record, serving in the Peninsular Wars and writing about them in later years. He also wrote 'The Castellated Architecture of Aberdeenshire', published in 1810, which features his own lithographs, including an entry on Leith Hall. He died in 1862. He was succeeded by his eldest son, Colonel Alexander Sebastian Leith-Hay CB, who by 1885 held 26,000 acres in Aberdeenshire, and who added the west front of the house in 1868 in Scottish Baronial style, and created the East Garden. In 1900 the East Porch and Entrance Hall were added by his nephew Charles Leith-Hay, who married the Hon Henrietta O'Neill. Together they extended the gardens to the west and created the rock garden. The East Garden was let out as a market garden during World War II and only the vegetable gardens were kept up from then until 1965, when they were restored by Colonel and Mrs P. Gascoigne, Mrs Leith-Hay's niece and her husband. The Hon Mrs Leith-Hay made Leith Hall over to the National Trust for Scotland in 1945.