Large scale simulations of macromolecules in solution that do not suffer from artifacts arising from force truncations are becoming feasible. New force evaluation algorithms such as the fast multipole method (FMM) and multiple time scale integration methods such as the reversible reference system propagator algorithm (r-RESPA) have been combined and used to perform fast and stable simulations of large macromolecular systems. A consistent treatment of the long-range forces in simulations with periodic boundary conditions requires the use of a periodic form of the Coulomb potential. In this article, the FMM is extended to periodic systems, and combined with RESPA, yielding a new algorithm that is successfully applied to the simulation of large biomolecules in solution. If the interactions at different stages are separated smoothly, good energy conservation is obtained even for time steps as large as 12 fs on a system of over 40 000 atoms, and a CPU speedup of more than a factor of 20 is achieved compared to the standard Verlet integrator with Ewald sum for the Coulombic interaction. As compared with the recently developed particle-mesh Ewald (PME) method, the periodic r-RESPA/FMM has a break-even point at about 20 000 atoms; for larger systems, r-RESPA/FMM is expected to be more efficient.