To nondestructively test residual stress in materials, a time of flight measurement of ultrasonic propagation is proposed based on phase-frequency relationship and then an ultrasonic characterization of residual stress is developed based on acoustoelasticity, in which a combined measurement of longitudinal and transverse waves are used. The proposed ultrasonic measurement of residual stress can be applied not only to test the residual stress with a dual-directions, but also to make an exquisite measurement of time of sound flight in a short distance. The accuracy can reach to a sensitivity of 0.3 ns for the specimen of 9 mm’s length under a stress load of 20 MPa. The proposed method is carried out to measurement the distribution of residual stresses in the welded joints of 16Mn steels. Then, theoretical computations and X-ray diffraction also are used to verify the measured results. The result shows that the proposed ultrasonic method has a good repeatability and reliability in experiments, which can be used to test residual stress for welded joints in two axis directions.