In the lower part of the garden, the archaeological research revealed production areas and thoroughfares from the 13th century (the production areas are probably older). A thoroughfare went through a part of the current garden in the Middle Ages, towards the main (southern) gate of the Prague Castle, prolonging the street U Zlaté studně. The remains of the thoroughfare were destroyed during the building of the Baroque terrace garden. Another important thoroughfare went through the adjacent house No. 163-III. Its inconspicuous façade conceals the preserved tower core of a medieval house, unique in the Lesser Town.

In the 14th century, at least two houses had been standing on the site where the palace was built later. Both houses were damaged by the big fire of the Lesser Town and Hradčany in 1541, and were reconstructed in the renaissance style. Both were bought in 1665 by John Wenceslas of Kolowrat, who united them into a single building and improved them significantly (1669). In 1697, the spectacular building was bought by the Trauttmannsdof family (Maria Charlotta and Leopold Anton), who owned it until 1727. The Trauttmannsdorfs are known for their development of the garden; however, the garden had almost certainly existed already in the Kolowrat era. The basic plan has been so far early Baroque, from the 17th century, so we can assume it was established between the end of the major reconstruction (1669) and the sale to the Trauttmannsdorfs, i.e. in the 1670s or 1680s. Either the Kolowrats or the Trauttmannsdorfs also established the first sala terrena in the upper floor of the northern palace wing; its ceilings are decorated by typical big-shaped stucco work of the late 17th century. Its opening to the garden was removed in the 19th century at the latest.

The second, still existing, sala terrena in the extension of the western wing is younger; it was built in the 1720s. In the past, it was believed that the author was Giovanni Battista Alliprandi or Franz Maximilian Kaňka (both of them worked for the Trauttmannsdorf family, especially in Litomyšl), but this is unlikely. Some elements of the structure, such as the wavy central part, are strikingly similar to the concept of the façade of St. Havel’s church in the Old Town, where Kaňka’s teacher Paul Ignatius Bayer worked (he lived a very long life until 1733). However, there are no solid documents related to the building of sala terrena.

In 1783, the palace was acquired by Joseph Krakovský of Kolowrat, who then in 1801 bought the westernmost part (with the second passage) and then unified the whole building in 1802, according to the plans made by Ignatius John Nepomuk Palliardi. Hence the current appearance of the palace, including the front face.

In 1852, the palace was acquired by the Ledebour house, who did mainly indoor reconstructions (including the rear building). After one of them at the latest (1863), the connection between the older sala terrena and the garden was removed and replaced by simple rectangular windows.

After 1945, the palace was a part of the larger set of buildings used by the Ministry of Information, which initiated the first – and unsuccessful – public access to the gardens.

In 1995, a Romanesque wall with a portal was discovered on the site – it’s Písek Gate. The discovery proves that the Lesser Town was fortified already in the Romanesque era, in the mid-12th century at the latest. The appearance of the “gate” strongly resembles the Romanesque portals of the Black Tower at the Prague Castle. The Romanesque rampart wall marks the eastern border of the site; the buildings that belonged to the town were built west of this wall. The first buildings were documented here in the 15th century, and they were (like the neighboring ones) destroyed by a big fire of the Lesser Town and Hradčany in 1541.

In 1709, the two houses standing on the site were bought by John Joseph Wallenstein. In 1712, his “Prague house” was, as the aristocratic property, exempted from the town jurisdiction. The major reconstruction between 1715 and 1720 was supervised by Franz Maximilian Kaňka, the frequent architect of the Wallensteins and the one who worked for them also in Duchcov. Kaňka used the existing structure to create a spectacular trapezoid palace plan. His authorship remained unknown in the expert literature for a long time, also due to the simple appearance of the outer façades; nowadays, it’s not only acknowledged but reliably proven. The simple design of the façades was an explicit request of the sponsor, Count Wallenstein. Typically for F. M. Kaňka, the palace had elaborate interiors and luxurious equipment, for which Wallenstein paid large amounts of money. However, the interiors were largely modified in the 19th century. Like in Duchcov, the garden was built together with the palace, so Kaňka’s authorship is unambiguous.

The following owners of the Fürstenberg house renovated the palace around the years 1808, 1810–1823. They also reconstructed the gardens – obviously modified the parterre and planted trees. In 1856, the houses No. 156-7-III were torn down, which caused the empty space between Pálffy and Kolowrat Palace, and it was necessary to adjust the exposed eastern face of the building. Eduard Pálffy bought the palace in 1881, but he did only minor adjustments and sold the building to the state in 1902.

After 1950, the palace was used by the Ministry of Information.

Sometimes, this garden is divided to the Kolowrat (next to the building No. 154-III) Small Fürstenberg (next to The Small Fürstenberg House, No. 155-III). However, these gardens used to be a single complex with the palace No. 154-III; using the aforementioned description, the garden can be mistaken for the Fürstenberg Garden at the Fürstenberg Palace, No. 153-III.

The sites outside the Lesser Town ramparts weren’t built-up with permanent residential houses until the 16th century; the first records of such buildings appeared at the end of the century. In 1601, the area was bought by Wilhelm of Lobkowicz, who started the construction, but when his property was confiscated after the Battle of White Mountain, the place was claimed by the abbess of St. George’s monastery at the Prague Castle who, among other things, complained that Lobkowicz hadn’t been allowed to build a permanent stone residential building on the land belonging to the monastery. Of course, she also required compensation for the unpaid rent. These problems dragged on, to reach a partial settlement in 1661 when the palace belonged to the Götz house. In 1621, the site was still described as remote, even though the construction of the Wallenstein Palace was already in preparation. The main problem, however, was that the site was located in two different jurisdiction areas – as far as the documents go, the left and the central part belonged to the town (town-owned sites in front of the ramparts), while the right (easternmost) one was owned by the St. George’s monastery (as the farming land, probably the vineyard but it’s not sure whether it covered the whole area). The unusual legal situation is also reflected in the atypical design of palace wings situated sideways to the street line, also irregular. The renaissance building of Wilhelm of Lobkowicz, also irregular, is the core of the whole complex. Despite the reconstruction in the 17th century, the palace house remained built in renaissance style, so Maria Barbara Černín of Chudenice bought it in 1759 for rather a low price.