Failure of one upper anchorage element in a cable-stayed bridge and its consequent analysis concluded that the main cause of the failure was a deficient heat treatment that resulted in large micro structural grain size and low fracture toughness, vulnerable to fatigue damage. Previous research studies demonstrated that ultrasonic evaluation could provide some insight of the microstructural integrity by correlating the ultrasonic response to the grain size. Thus, this technique was used to inspect the 112 elements in service in the bridge and 16 were qualified as structurally deficient, without direct verification of the grain size, since these elements were partially embedded in the concrete structure. Late rehabilitation of the bridge considered the replacement of the 16 structural deficient anchorage elements, plus 4 elements qualified in good condition, to complete a reliability analysis for the remaining 92 elements from the statistical mechanical properties of the removed pieces. Rehabilitation made possible the confirmation of the initial diagnosis made by ultrasonic inspection and fatigue cracks were identified in some elements. This study demonstrated that the ultrasonic non destructive evaluation is highly reliable for structural integrity qualification of steel structural elements partially embedded in concrete.