The historical sources of 1579 mention a International Gothic building in the same place. However, it later fell into disuse and then into ruin. Around 1765 the parcel was bought by Antoni Tyzenhaus (Antanas Tyzenhauzas in Lithuanian translation), a treasurer of Lithuania, starost of Grodno and a close friend of the Polish king Stanisław August Poniatowski. A notable personality of the epoch, Tyzenhauz was a manager of royal grounds in the Grand Duchy of Lithuania and was responsible for a major industrialisation effort in the area of Grodno. In the early 1770s he ordered the construction of a new, classical style palace.
The house was most probably constructed by a Venetian architect Giuseppe de Sacco. After Tysenhaus went bankrupt and was dismissed in 1777, the palace fell into disuse. After Tysenhaus' death in 1785, it was sold to General Fitinhof's widow. She bought the palace in 1789 and the following year she ordered its reconstruction and refurbishment. The work was most probably carried out by German-born architect and professor at the Jesuit Academy of Vilna Martin Knakfus. The new simplistic façades were added and a so-called Silver hall was built. After the reconstruction, the palace had 30 halls and 16 smaller rooms; and was one of the biggest aristocratic residences in Lithuania. In 1807, yet another refurbishemnt was carried out by Mikołaj Szulc, after which the interior was modernised and a new staircase was added to the palace.
Despite that, in 19th century the palace yet again fell into disuse and was parcelated between various shops and stores. Many doors and windows were added on the ground floor and the luxurious part of the palace deteriorated. In early 20th century the palace was bought by E. Bortkiewicz, who ordered the reconstruction of the second floor. Later, after the city of Vilnius/Wilno became a part of Poland in 1922, the 2nd and 3rd floors were yet again reconstructed to house a Hotel Sokołowskiego, named after its owner. During the German bombings of Wilno during the Polish Defensive War the building was heavily damaged. It was further damaged during Operation Ostra Brama in 1944, and only the cellars, ground floor and outer walls were preserved. Unlike many buildings on Vokiečių street, the palace was rebuilt in 1945. In 1957 the total reconstruction of the palace was led by Algimantas Umbrasas. As with most of the palaces at that time, it was reconstructed by the Soviet authorities to house small apartments. This was due to the shortage of living space in Vilnius caused by a great deal of residential buildings having been destroyed. A fourth floor was added, yet it is invisible from the outside of the palace.
After Lithuania regained her independence, downtown Vilnius became a prestigious place, and many of the occupants of the palace took the opportunity to sell their flats for a high price. Out of 40 flats that were carved out of the palace, most currently serve as either offices or shops.
The palace has 3 floors on the street side and 4 floors on the courtyard side. The courtyard is fully enclosed by the building and is accessible through 2 gates, one on each of the adjacent streets. The palace is of trapezoid form. On the street side, the building has a tall attic. It has 2-level gothic cellar, which is currently unused.
One of more interesting elements are sculpures which can be seen immediately beneath the attic on the street side; there are many different bas-reliefs. The rooms on the sides of building facing the street are in two lines: each room has windows opening on both the street and the courtyard. The walls facing the courtyard are narrower. Other exposures of the palace face other courtyards. The attic was unused following the rebuilding after World War II, but has been put to commercial use since the collapse of the Soviet Union.
It is on corner of two streets, and has two addresses: