The authors accelerate the replica exchange method through an efficient all-pairs replica exchange. A proof of detailed balance is shown along with an analytical estimate of the enhanced exchange efficiency. The new method provides asymptotically four fold speedup of conformation traversal for replica counts of 8 and larger with typical exchange rates. Experimental tests using the blocked alanine dipeptide demonstrate the method's correctness and show an approximate sampling efficiency improvement of 100% according to potential energy cumulative averages and an ergodic measure. An explicitly solvated PIN1 WW domain system of 4958 atoms is sampled using our new method, yielding a cluster sampling rate almost twice that of the single exchange near neighbor implementation. Computational software and scripts along with input and output data sets are available at.