Unconditional stability of the Crank-Nicolson Finite Difference Time Domain (CN-FDTD) method permits us to use time steps over the Courant-Friedrich-Lewy (CFL) limit of conventional FDTD method. However, in this work it was realized that, when the time step is set above CFL limit the coefficient matrix arising from Crank-Nicolson method is no longer diagonally dominant and iterative solvers require longer solution time in each FDTD iteration. Frequency dependent CN-FDTD (FD-CN-FDTD) scheme for Debye media is formulated and numerical tests are performed with two widely used sparse iterative solvers, Bi-Conjugate Gradient Stabilised (BiCGStab) and Generalised Minimal Residual (GMRES), for comparison. BiCGStab outperforms GMRES in every aspect of the study. © 2009 VSP.