Combining the interpolating element free Galerkin (IEFG) method and the self-adaptive precise algorithm in time domain, a novel algorithm is proposed for structural dynamic analysis in this paper. By expanding variables in each discretized time interval, the coupled spatial and temporal problem is transformed into a series of spatial problems, which are recursively solved by the IEFG method. The corresponding discretized governing equations for structural dynamic analysis are derived using the weighted residual technique. The proposed method can directly impose the essential boundary conditions directly and avoid possible loss of precision resulting from large time steps. The computational results shown in the numerical examples are satisfactory, which can demonstrate the effectiveness of the proposed method.