Construction began on May 15, 1918, with the city committing $40 million to the project. Gilbert, already famous for the Woolworth Building, designed two eight-story warehouses that ranked among the world's largest concrete structures when completed the following year. Warehouse B featured a central atrium with railroad tracks running through it, loading balconies staggered diagonally along the walls, and a five-ton overhead crane that swung cargo between levels. Three more tracks threaded the gap between the buildings. The complex included three two-story piers, a power house, a boiler room, and a train yard with capacity for 2,200 rail cars. It was a logistics machine on a scale that the 20th century was only beginning to imagine.

Between wars, the terminal found unexpected uses. In 1929, after a string of thefts, the Army built a heavily fortified vault on the seventh floor of Warehouse A. The Brooklyn Daily Eagle called it "the largest vault built anywhere for the storage of dangerous drugs," a room measuring several hundred feet in each direction. A laboratory on site tested confiscated alcohol during Prohibition -- beverages deemed suitable for future medicinal use were kept; the rest were dumped into New York Harbor. That lab closed in 1933 when Prohibition ended. In 1930, the government announced plans for a 125-prisoner military prison on the grounds, intended to house deserters and servicemembers convicted of serious crimes. The community protested the decision, but the prison went forward regardless.

During World War II, the Brooklyn Army Terminal became the largest military supply base in the United States. It employed 20,000 workers and served as headquarters for the New York Port of Embarkation. Contemporary accounts report that 43 million short tons of cargo passed through the complex and 3.5 million soldiers departed from its piers. After the war, the terminal took on a grimmer duty. In October 1947, the first boat carrying American war dead arrived in San Francisco, and the bodies were transported cross-country to Brooklyn. A ship carrying 4,212 soldiers' remains sailed directly to the terminal the following month. By July 1948, the base was receiving 18,500 bodies within a two-week span. The 328th Army Band, which had played soldiers off to war, now played them home.

Defense Secretary Robert McNamara announced the terminal's closure in November 1964 as part of a nationwide wave of base closings. Military operations ceased on January 1, 1967. What followed was a period of improvisation. When fire destroyed Manhattan's Morgan General Mail Facility in December 1967, postal operations shifted to the vacated terminal, which soon handled 18,000 bags of international mail daily with 4,000 workers. The Navy moved in during 1972, renaming the complex the Military Ocean Terminal. By 1975, the military had fully departed. The city purchased the property in 1981 for $8.5 million after contentious negotiations with the federal government, and the terminal was listed on the National Register of Historic Places in 1983.

The city began renovating Building B's northern half in 1985, adding a million square feet of leasable space at a cost of $33 million. Phase after phase followed over the next three decades -- Building A in the 1990s, additional wings through 2003, a food-manufacturing complex in the old Administration Building. By 2018, when the renovation of Building A's 500,000-square-foot space was completed, the terminal housed 100 companies employing 3,800 workers. The tenants today tell the story of Brooklyn's economic reinvention: the American Museum of Natural History stores collections here, the Guggenheim Museum uses warehouse space, Jacques Torres makes chocolate, and tech companies fill the floors where soldiers once stored gear. In 2024, solar panels were announced for the roof of Warehouse B. The following year, a climate innovation center backed by $100 million in city investment was planned for the site. The old train tracks in Warehouse B's atrium are overgrown now, two rusted rail cars permanently parked on the western track like artifacts in an unintentional museum. Outside, NYC Ferry boats dock at the piers where troopships once moored, carrying commuters instead of soldiers across the same gray water.