The tracking of magnetic field lines can be very expensive, in terms of computational burden, when the field sources are numerous and have complex geometries, especially when accuracy is a priority, because an evaluation of the field is required in many situations. In some important applications, the computational cost can be significantly reduced by using a suitable approximation of the field in the integrated regions. This paper shows how Chebyshev polynomials are well-suited for field interpolation in magnetic field-line tracking, then discusses the conditions in which they are most appropriate, and quantifies the effectiveness of parallel computing in the approximation procedures.