An acceleration scheme is proposed in a coupled ocean-atmosphere model for the simulation of long term climate evolutions forced by climate forcing of longer than millennia time scales. In this coordinated acceleration scheme, both the surface forcing and the deep ocean are accelerated simultaneously by the same factor. The acceleration scheme is evaluated in a 3-dimensional ocean general circulation model and in a coupled ocean-atmosphere model of intermediate complexity. For millennial climate evolution, our acceleration scheme produces reasonably good simulations with an acceleration factor of about 5. For climate evolution of even longer time scales, the acceleration factor can be increased further.