Holsteinborg Castle is a manor house located 12 kilometres (7.5 mi) southeast of Skælskør, Slagelse Municipality, Denmark. It was built in the first half of the 17th century by members of the Trolle family, who gave it the name Trolholm, but has been owned by the Holstein family since 1707. Hans Christian Andersen was a frequent visitor to the estate in the middle of the 19th century. The main building is situated close to the coast, overlooking Holsteinborg Nor, a shallow watered cove which is almost closed off from the Småland Sea and Great Belt by Glænø, Glænø Stenfed and Glænø Østerfed.

A fortification was built in about 1200, approximately at the site of the current castle to guard Bisserup Harbour, then a naval support point. The estate was referred to as Bråde in 1357 when it was owned by the Roskilde bishopric. The property was confiscated by the Crown 1536 in connection with the Reformation.

In 1562, King Frederick II ceded the estate to Niels Trolle, a younger brother of Herluf Trolle, in exchange for his holdings in northern Zealand. Niels Trolle was killed in the action of 7 July 1565 on Bornholm in 1565. His son, Børge Nielsen Trolle, changed its name to Trolholm in 1682. Børge Trolle commanded a flotilla attending Christian IV on his Arctic exploration in 1599. The voyage is described by the author Thorkild Hansen in Jens Munk. Børge Trolle's son, Niels Trolle, who owned Trolborg from 1615–1667, served as Steward of Norway from 1657 until 1661. The estate was owned by members of the Trolle family until 1707.

Ulrik Adolf Holstein acquired the Barony of Fuirendal in 1700. In 1707, he also acquired Trolholm and Snedinge. Holstein was created Count of Holsteinborg in 1708. He built ten village churches on his estate and expanded Holsteinborg Church in 1728. He served as Grand Chancellor during the last ten years of Frederick IV's reign.

Frederik Adolph Holstein, 6th Count of Holsteinborg, belonged to Reventlow and Bernstorff's social circle. He also brought the Christmas tree tradition to Denmark when the first Danish Christmas tree was lit on Christmas Eve 1808 at Holsteinborg.

Ludvig Holstein-Holsteinborg, 7th Count of Holstein, who served as Council President in the early 1870s, owned Holsteinborg from 1836 to 1892. Hans Christian Andersen was a frequent visitor to his homes, both in Copenhagen and at Holsteinborg. Andersen made his first visit to the estate in May 1856, noting in his diary that "The food was sumptuous, I was placed in a very elegant bedroom and a cabinet facing the great courtyard, which is rather similar to that of Kronborg".

The building was restored in 1949–1950 under the supervision of H. H. Engqvist.

The oldest part of the four-winged manor house is the west wing which was built by Børge Trolle in 1598. The three other wings were built between 1538 and 1546. The building was adapted in 1777–1781 by G.E. Rosenberg and again in 1848–1850 by Gustav Friedrich Hetsch. The original Renaissance castle now combines Gothic, Renaissance, Baroque and Neoclassical elements. The main gate is located in the north wing which is flanked by corner towers with spires from 1642 and 1649. The two headless shieldbearers that flank the gate represent the headless troll in the Trolle family's coat of arms. The moat is only preserved on the north side and around the farm buildings, some of which date from the middle of the 17th century.