Two-frame phase shift extraction algorithm is characterized by small number of fringe patterns and fast processing speed. However, there are many challenges related to the design of this algorithm because of the pathological problems associated with the two-frame phase shift technology. In this study, a phase shift extraction algorithm is proposed for a two-frame random time-domain phase-shifted fringe pattern. First, the background term of the fringe pattern was eliminated using high-pass filtering. Subsequently, the minimum square root of the amplitude was searched using the gradient descent algorithm in combination with the square root distribution law of amplitude. Then, the introduced phase shift was extracted. Finally, the two-step phase shift algorithm was used to obtain the measured phase. The simulation and experimental results show that compared with other classical algorithms, the proposed algorithm exhibits various features, including small recovery phase error and noise insensitivity. Furthermore, the proposed algorithm is simple, flexible, and easy to apply.