Reversible computation plays an important role in the synthesis of circuits having application in quantum computing, low power CMOS design, bioinformatics and nanotechnology-based systems. Conventional logic circuits are not reversible. A reversible circuit maps each input vector, into a unique output vector and vice versa. We demonstrate how the well-known and very useful, Toffoli gate can be synthesized from only two parity-preserving reversible gates. Parity preserving reversible gates refers to those reversible gates for which the parity of the outputs matches that of the inputs. The proposed parity preserving Toffoli gate renders a wide class of circuit faults readily detectable at the circuit’s outputs. It allows any fault that affects no more than a single signal to be detectable at the circuit’s primary outputs. We show that our proposed parity-preserving Toffoli gate is much better in terms of number of reversible gates, number of garbage outputs and hardware complexity with compared to the existing counterpart. Then we apply the proposed fault tolerant Toffoli gate to the design of a fault tolerant reversible full adder, which is a versatile and widely used building block in computer arithmetic.