The palazzo was first built by cardinal Michele Bonelli, nephew of pope Pius V, who, in 1585, acquired a pre-existing palazzo from Giacomo Boncompagni at the extremity of what was then piazza dei Santi Apostoli. Today the palazzo is separated from that piazza by via Quattro Novembre, opened later to connect the new via Nazionale with piazza Venezia. The cardinal was also the owner of a large part of the area which extended, behind the palazzo, above the ruins of the imperial fora of Trajan and Augustus, known by the name "Pantano" due to its being subject to impaludamenti. Over the same years the district on the ruins of the imperial fora was subjected to a general development of the land and to a systematic urbanisation, with the creation of the "quartiere Alessandrino" in the cardinal's honour (he was nicknamed "cardinale alessandrino" after his origins in a village in the province of Alessandria). The quarter was destroyed in the 1920s and 1930s to open via dei Fori Imperiali.
The trapezoidal plan of the palazzo was designed by Domenico Paganelli. Thanks to substantial funds ploughed into the project by the cardinal, the palazzo was quickly completed and the cardinal moved in 3 years after building started. In the 17th century the building was then subject to a series of major renovations and expansions, carried out on behalf of cardinals Carlo Bonelli and Michele Ferdinando Bonelli. The palazzo was partially demolished and rebuilt by Francesco Peparelli for its new owner, cardinal Renato Imperiali, who organised the important family library (the "Imperiali") of around 24,000 volumes.
At the start of the 18th century, the palazzo was leased to several prominent personalities, including marchese Francesco Maria Ruspoli from 1705 to 1713, who made it the site for a private theatre and hosted illustrious musicians of the time such as Handel, Alessandro Scarlatti and Arcangelo Corelli. The entire building was then acquired in 1752 by cardinal Giuseppe Spinelli, who realised a new decorative scheme for the first floor and systematised the library (meant by him for public use, and frequented by Johann Joachim Winckelmann) on the ground floor.
In 1827 the Prussian banker and consul general Vincenzo Valentini acquired the palazzo, in which he settled and to which he gave his name. The palazzo was later expanded and rebuilt at great expense, and its new owner used it to house his own collection of paintings as well as increasing the palazzo's own substantial library and archaeological collection. Completion of the works at the back of the palazzo, overlooking the column of Trajan, was entrusted to the architects Filippo Navone and Giovanni Battista Benedetti. Between 1861 and 1865 Vincenzo's son Gioacchino Valentini commissioned two further expansions on the left side, along via di Sant'Eufemia, designed by the architect Luigi Gabet. The provincial deputation of Rome acquired the palazzo as their base in 1873, commissioning the architect Gabet to complete the right side on via de’ Fornari, at the top of vicolo di San Bernardo.
The present structure of the palazzo is characterised by its grand portal, pierced by three windows on each sides, with architraves and lintels and bounded by two travertine columns. Above it is a large balustraded balcony. The great cornice, under which are small windows divided by three mensoloni, is surrounded by a balustrade. The courtyard is a portico in two orders and with 5 arcades on the short sides and 9 along the long sides, divided by Doric pilasters and rich in ancient statues.
The Palazzo's art treasures include the statue of Ulysses by Ugo Attardi, as well as works depicting "Aeneas and Anchises" and "Europa", made by Sandro Chia to commemorate the 135th anniversary of the provincial administration of Rome, now located at the entrance.
After a major restoration the excavations under Palazzo Valentini have now opened to the public on a permanent basis. A small baths complex dating from the 2nd century AD was discovered seven metres below street level under the basement of the building. It is believed to be part of a nearby residential scheme found over 100 years ago prior to the 1907 construction of Palazzo delle Assicurazioni in Piazza Venezia.
Recent excavations in the palazzo's basement have found, around 7m below street level, a small baths complex, probably part of an adjacent residential complex already found in 1902 during surveys for the construction of Palazzo delle Assicurazioni di Venezia.
The monumental temple of the deified Trajan was traditionally thought to have been on the same site as this palazzo, but no trace of it has been found here.