Plans are underway to replace the current structure with a new nine-lane bridge, which will consist of two eastbound spans, one westbound span, a bike path, and a walkway. Four designs were considered for the new structure: a cable-stayed bridge, a through arch bridge, a box girder bridge, and a deck arch bridge. The cable-stayed bridge design selected after a public review process will make the replacement bridge the first of its type in New York City since the Brooklyn Bridge (which has a hybrid suspension/cable-stayed design). Construction was originally expected to begin in 2013 but will now begin in winter 2014. About 140 trees were removed on both sides of the bridge in April 2014 in preparation for the rebuilding, though officials say twice the number of trees will be replanted once the bridge's reconstruction is complete.
On May 23, 2014, a $554,770,000 design-build contract was awarded to a team consisting of Skanska, which will be managing partner, Ecco III of Yonkers; Kiewit Corporation of Nebraska; and HNTB of Kansas as the lead design firm. It is the largest single contract ever awarded by the New York State Department of Transportation. The work will involve building a new eastbound viaduct to be completed in 2016. The existing eastbound structure will then be demolished. The westbound viaduct will be replaced in a future project. The extra lanes are being built since the Kosciuszko Bridge is known as a notorious traffic bottleneck; according to The New York Times, it is "perhaps the city’s most notorious [bridge], hated and feared by drivers and synonymous in traffic reports with bottlenecks, stop-and-go and general delay."