The criteria used for successful rehabilitation of decks of major bridges when it is not feasible to close the bridge to traffic are described. These criteria are described with specific reference to recent work on the trestle spans of the Tappan Zee Bridge over the Hudson River near New York City. The results of an experimental program conducted with a full-scale, 10-m-span, lightweight concrete slab-steel beam composite bridge deck unit intended for later use in rehabilitating the through-truss decks of the bridge are also described. Loading history included 10,000,000 cycles of flexural fatigue loading followed by a flexural load capacity test. Measured values of capacity and midspan deflection at this ultimate load level are compared with simplified analytical predictions. A description of the actual rehabilitation process used on the Tappan Zee Bridge deck is also provided.