In many engineering problems, it is customary to use viscoelastic materials in the passive control of structural vibration and noise radiation. The most commonly used numerical tool to obtain detailed information on the performance of complex structures is the finite element (FE) method. However, structures with viscoelastic materials often require very large-scale FE computational models to obtain reliable predictions, which makes original full-order system evaluation intractable due to memory and time limitations. In order to alleviate these problems, model order reduction techniques have become indispensable. Most of them, however, often do not handle complex-valued and especially frequency-dependent system matrices well. Due to the frequency dependency of the material properties, the FE equations of motion for viscoelastic models are not of a standard second-order form as that for regular elastic FE models. In this paper, a new transformation technique based on Taylor’s theorem is introduced to treat the frequency-dependent shear modulus. After transforming the problem into a second-order system equation with remainder term, an adaptive second-order Arnoldi method is applied for the reduction of the computational complexity of structures, incorporating classical free- and constrained-layer damping treatments. In support, a relative error indicator is developed to iteratively enrich the reduced model and determine the position of expansion points used in next step. Three widely used models, the Golla–Hughes–McTavish model, Generalized Maxwell model and Fractional Derivative model for describing the frequency-dependent property of viscoelastic materials are investigated in order to demonstrate the simplicity, versatility and efficiency of the proposed approach.