Despite progress in managing TB, there were 8.6 million new cases in 2012. To control TB will require a more effective vaccine than BCG, new drugs and better diagnostic tests. Recombinant replication-defective adenoviruses expressing foreign DNA have been studied as vaccines. We developed and evaluated a recombinant replication-deficient human Ad5 vector expressing Ag85A (Ad5Ag85A) as a TB vaccine in animal models and a Phase I human study. Animal models of Ad5Ag85A show markedly improved protection over BCG alone and immunization via the respiratory route provides the best type of protection. In humans, intramuscular vaccination was safe; Ad5Ag85A was immunogenic and stimulated polyfunctional T cell responses, more potently in previously BCG-vaccinated volunteers. Pre-existing Ad5 antibodies did not dampen the response. Given its potency, Ad5-based TB vaccines are well-positioned to be delivered to the respiratory tract, induce local lung immunity to control TB, and inform innovative approaches to new TB vaccination strategies.