Wauna Toll Bridge Company contracted the construction work to Union Bridge Company out of Portland. The company promised to pay the contractor half of all toll receipts between June and September in the year following completion to motivate them to complete the project quickly. They began preparing for work in November 1925 to take advantage of low water and make allowances for poor weather conditions.
Union Bridge Company chief engineer R.M. Murray updated the design to create the steel cantilevered bridge in 1925. Murray also designed the Snake River Bridge and Twin-Falls Jerome Bridge.
Franklin W. Johnson came to Cascade Locks as local engineer for the Oregon side, and Lester S. Tubbs came to Stevenson as the local engineer for the Washington side. Johnson and Tubbs were recent alumni of the Oregon Agricultural College, now Oregon State University. They kept in contact with engineering faculty throughout the project and invited engineering students to inspect the bridge.
Union Bridge Company subcontracted with the Puget Sound Bridge and Dredging Company. They brought in 50 men to complete the construction in January 1926. They worked in two crews, one on each side of the river to complete the lowest elevation work at the lowest water levels. A night crew was hired in February 1926 to get as much work done as possible before high water arrived in the spring.
In March 1926, the crew blasted the top 10 feet off of the first concrete pier with dynamite. The pier needed to be made larger to support the new steel cantilever design. The second concrete pier on the Oregon side was completed in April, and three piers on the Washington side soon followed. Stevenson company Hazard & Allen was contracted to complete the gravel and earth work for the Washington approach.
The Union Bridge Company allowed filmmakers to document the process of building the Bridge of the Gods.