Never have the citizens of Norfolk so thoroughly scorned a work of architecture as they have the Federal Building. The need for such a building became apparent soon after World War II, when federal agencies began to outgrow the U.S. Post Office and Courthouse (now the Walter E. Hoffman Courthouse) several blocks north on Granby Street (see entry, below). It took nearly twenty years, however, for the plans to reach fruition and for the enabling legislation to be passed. To make way for the building, the Monticello Hotel (1899), a beloved city landmark, was razed, an act that proved ominous for the building's public reception.
As originally designed, the eight-story building was constructed of red brick with red mortar in the International Style. The main facade faced what was then known as Granby Mall, with a parking garage built into its base along Monticello Avenue to the rear of the site. A freestanding red steel arch—in reality two posts and a lintel—marked the main entrance on the mall side. Initial criticism focused on the red mortar, but soon the $14.5 million building exhibited other, more serious construction flaws. The windows leaked, and after several years, the brick cladding began to separate from the skeletal frame. In 1993–1996 the building was entirely reclad with white, cast concrete panels and reglazed at the additional cost of $6 million. Belt courses of thin aluminum were added to unify the exterior at the second-floor and roof levels, and the garage was screened with aluminum grates. To banish forever the taint associated with the building's red color, the “arch” was painted green. The Granby Street plaza contains an abstract sculpture by Athena Tacha, entitled Ripples.