Fast and accurate analysis of double-negative materials (DNMs) with the surface integral equations and the multilevel fast multipole algorithm (MLFMA) is considered. DNMs, which are commonly used as simplified models of metamaterials at resonance frequencies, can be formulated with the surface integral equations. Two recently developed formulations-namely, the combined tangential formulation (CTF) and the electric and magnetic current combined-field integral equation (JMCFIE)-are used to formulate DNMs. Iterative solutions with MLFMA are investigated in detail to show that numerical results are consistent with those for ordinary materials. Accuracy and efficiency of the proposed implementation based on JMCFIE with high combination parameter and MLFMA are demonstrated on very large problems discretized with tens of millions of unknowns.