The total focusing method (TFM) has been increasingly applied to weld inspection given its high image quality and defect sensitivity. Oblique incidence is widely used to steer the beam effectively, considering the defect orientation and structural complexity of welded structures. However, the conventional TFM based on the delay-and-sum (DAS) principle is time-consuming, especially for oblique incidence. In this paper, a fast full-matrix imaging algorithm in the Fourier domain is proposed to accelerate the TFM under the condition of oblique incidence. The algorithm adopts the Chebyshev polynomials of the second kind to directly expand the Fourier extrapolator with lateral sound velocity variation. The direct expansion maintains image accuracy and resolution in wide-angle situations, covering both small and large angles, making it highly suitable for weld inspection. Simulations prove that the third-order Chebyshev expansion is required to achieve image accuracy equivalent to the TFM with wide-angle incidence. Experiments verify the algorithm’s performance for weld flaws using the proposed method with the transverse wave and the full-skip mode. The depth deviation is within 0.53 mm, and the sizing error is below 15%. The imaging efficiency is improved by a factor of up to 8 compared to conventional TFM. We conclude that the proposed method is applicable to high-speed weld inspection with various oblique incidence angles.