Toeplitz-structured linear systems arise often in practical engineering problems. Correspondingly, a number of algorithms have been developed that exploit Toeplitz structure to gain computational efficiency when solving these systems. Early “fast” algorithms required operations, but recent “superfast” algorithms are more efficient. In this work, we present a superfast algorithm for Tikhonov regularization of Toeplitz systems. Using an “extension-and-transformation” technique, our algorithm translates a Tikhonov-regularized Toeplitz system into a type of specialized polynomial problem known as tangential interpolation. Under this formulation, we can compute the solution in only operations, where is the number of regularizers and is on the order of the number of parameters defining the system matrix. Our algorithm is further improved with displacement structure, which reduces the complexity when solving the system for multiple input vectors. We use numerical simulations to demonstrate our algorithm's complexity and accuracy.