The 1906 French Renaissance style brick and limestone building was designed by Carrere and Hastings, following the consolidation of New York City in 1898.

John Carrere was a resident of Staten Island and he helped select the dramatic hilltop site of Borough Hall.

The interior of the building contains a series of thirteen WPA murals illustrating events in Staten Island history, painted by local artist Frederick Charles Stahr.

Working out of a third-floor studio, Stahr created storybook style oil paintings on canvas over the next two years, which were cemented to Borough Hall's walls as he went along.

The thirteen murals depict Verrazzano's discovery of Staten Island in 1524; Henry Hudson's 1609 visit aboard the Dutch ship Halve Maen; two panels showing stoic Lenape natives trading furs for trinkets; French Huguenot farmers; British Admiral Howe taking charge of the island in 1776 and creating Fort Hill; the 1776 peace conference among Howe, Benjamin Franklin, John Adams and Edward Rutledge at the Conference House in Tottenville; the so-called Battle of St. Andrew's; British ships departing during Evacuation Day in 1783; the erection of Fort Richmond and Fort Tompkins in anticipation of the War of 1812; a stagecoach stopping at the Black Horse Tavern, which had been destroyed to accommodate road widening in 1934, three years prior to the 1937 painting; the Hotel Castleton, run by freed black men in the 19th century and destroyed by fire in 1907; the first Clifton to Tottenville railroad in 1860; and, finally, the Bayonne Bridge, showing a snappily-dressed Othmar Ammann, the bridge's designer, watching its construction sometime between 1928 and 1931.