We show that one can implement the Deutsch-Josza algorithm, one of the first and simplest quantum algorithms, in a fault-tolerant manner using the smallest quantum error-detecting code -- the
[[4,2,2]] code -- without any ancillae. We implemented the algorithm on a trapped-ion quantum computer with and without fault-tolerant encoding and compared the results. With approximately
99% confidence, we found that the fault-tolerant implementation provided a noise reduction for all oracles. Averaged across all oracles, the reduction in error rate was nearly
90%.