We consider the solution of delay differential equations by using boundary value methods (BVMs). These methods require the solution of some nonsymmetric, large, and sparse linear systems. In this paper, these systems are solved by using the GMRES method. A mixed-type block-circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. If an A ink,k-stable BVM is used and the system matrices of delay differential equations are normal, then the BCCB preconditioner is invertible. The advantage of using such kind of preconditioner is that we can use two-dimensional fast Fourier transform to reduce the operation cost. Numerical results are given to show the effectiveness of our methods.