Roebling's plan was to erect two massive towers of stone, each standing 268-feet tall and weighing nearly 68,000 tons, built with gothic arches through which the roads would run. The towers had to be large and strong enough to bear the weight of suspended steel cables that connected to the roadway, including the upward force of the cables on the roadway and the downward force where they passed over the tower-tops. In addition, four thick steel cables would run under the length of the roadway's span across the river, connecting to the towers at each end. Perhaps most remarkable and far-sighted in Roebling's design was his use of steel, particularly in the cables, for strength and durability. No other bridge or building to date had been so dependent on steel, "the medal of the future," in the words of the engineer. The bridge would be over a mile long and able to bear almost 19,000 tons.

In early 1867, Roebling presented his plan to William C. Kingsley, a wealthy Brooklyn contractor and publisher of the Brooklyn Eagle, who was impressed. Kingsley contacted State Senator Henry C. Murphy of Brooklyn, who steered through the state legislature a charter for the New York Bridge Company (for which Murphy was president and Kingsley was chief contractor). In order to gain support for the project in Manhattan, Murphy bribed New York aldermen and gave Tammany Hall boss, William Tweed, and two of his colleagues nearly half of the remaining private stock in the venture. Passage of the charter was also helped by the cold winter of 1866-1867, which had emphasized the vulnerability of ferry crossings in the ice-laden waters of the East River.

In May 1867, Roebling was named the chief engineer for the suspension bridge, which was called the East River Bridge by Roebling and the New York Bridge by Brooklyn residents (who saw it as a bridge to New York), but most commonly, the Roebling Bridge, the Great Bridge, or the Brooklyn Bridge. Roebling began hiring a crew and making preliminary plans for construction. He had nearly completed his task in June 1869 when the U.S. Congress, which had oversight of all navigable rivers, approved the project. Later that month, however, tragedy struck when a ferry hit a waterfront piling, crushing Roebling's foot and causing lockjaw, seizures, a coma, and, finally, death on July 22. His son, Washington Roebling, was appointed as the new engineer of the Brooklyn Bridge.

Construction began in January 1870, and in May, laborers were lowered into the water in caissons (large, bottomless but watertight, chambers), where they worked around the clock (except Sundays) digging for bedrock. A year later the towers began to emerge above the water level. While submerged in a caisson in 1872, Washington Roebling suffered from decompression sickness (a common problem for the workers, called "caisson disease" at the time and "the bends" today), which left him paralyzed for the rest of his life.  However, he continued managing the project by monitoring bridge construction through a telescope from his bedroom window in his Columbia Heights (Brooklyn) home, and relaying directions through his wife, Emily, to the site engineers.

Construction of the Brooklyn Bridge was hazardous, resulting in the deaths of 26 men in addition to John Roebling from various accidents involving snapping cables, falling masonry, and "caisson disease" (three from the latter). The difficult, dangerous conditions of the caisson workers prompted them to strike in 1871 for higher wages. The New York Bridge Company agreed to an increase that was less than what the workers wanted, but a threat to fire them all ended the strike. Other problems included defective wire rope that had to be replaced (1878) and a financial shortfall until additional appropriations were made (1879). Nevertheless, work continued, with the Brooklyn tower completed in June 1875 and the New York tower a year later. The steel cables were then connected over the towers in August 1876 to the jubilation of tens of thousands of spectators, who cheered as cannons boomed and church bells rang.

On May 24, 1883, schools and businesses across the metropolitan area closed so that New Yorkers could attend the opening ceremonies for the Brooklyn Bridge. Honored guests included President Chester Arthur, Governor Grover Cleveland, and the mayors of Brooklyn and New York. The Brooklyn Bridge was celebrated as the "new eighth wonder of the world," and compared by poet Walt Whitman to Columbus's discovery of America. The opening of the bridge to pedestrian traffic a week after its official opening unfortunately saw the death of twelve people, who were crushed in a panic caused by the shouted false warnings that the bridge was collapsing. The Brooklyn Bridge was the longest bridge in the world until surpassed by a Scottish bridge in 1890, and became the cultural and engineering landmark that John Roebling had predicted in 1867.