The solution of the total least squares (TLS) problems, minE,f ?(E,f)?F subject to (A + E)x = b + f, can in the generic case be obtained from the right singular vector corresponding to the smallest singular value sn+1 of (A, b). When A is large and sparse (or structured) a method based on Rayleigh quotient iteration (RQI) has been suggested by Björck. In this method the problem is reduced to the solution of a sequence of symmetric, positive definite linear systems of the form (ATA - s¯2I)z = g, where s¯ is an approximation to sn+1. These linear systems are then solved by a preconditioned conjugate gradient method (PCGTLS). For TLS problems where A is large and sparse a (possibly incomplete) Cholesky factor of AT A can usually be computed, and this provides a very efficient preconditioner. The resulting method can be used to solve a much wider range of problems than it is possible to solve by using Lanczos-type algorithms directly for the singular value problem. In this paper the RQI-PCGTLS method is further developed, and the choice of initial approximation and termination criteria are discussed. Numerical results confirm that the given algorithm achieves rapid convergence and good accuracy.