Toxoplasma gondii is an intracellular parasite widely spread around the world. The Surface Antigens (SAG) 1, 2 and 3 are the main proteins expressed on the surface of T. gondii tachyzoites. Replication-defective adenovirus serotype 5 (rAd5) is one of the most potent recombinant viral vectors for eliciting T cell-mediated immunity in mice and humans. Here we show that vaccination with rAd5 expressing SAG1 (AdSAG1), but neither SAG2 nor SAG3, induces protective immunity in the highly susceptible C57BL/6 mice challenged with T. gondii. Furthermore, we evaluated different immunological components involved on viral induced protective immunity. We observed that host protection elicited by AdSAG1 is highly dependent on IL-12, IFN-γ and CD8+ T lymphocytes. Importantly, the induction of protective immunity (T cell-derived IFN-γ) was also dependent on Myeloid Differentiation Factor 88 (MyD88), and thus, likely to involve Toll-Like receptors. We conclude that protective parasite specific-CD8+ T cells are elicited by a mechanism that involves MyD88-dependent induction of IL-12.