Scrub typhus is a severe mite-borne infection caused by Orientia tsutsugamushi, an obligately intracellular bacterium closely related to Rickettsia. The disease explains a substantial proportion of acute undifferentiated febrile cases that require hospitalization in rural areas of Asia, the North of Australia, and many islands of the Pacific Ocean. Delayed antibiotic treatment is common due to the lack of effective commercially available diagnostic tests and the lack of specificity of the early clinical presentation. The systemic infection of endothelial cells that line the vasculature with Orientia can lead to many complications and fatalities. In survivors, immunity does not last long, and is poorly cross-reactive among numerous strains. In addition, chronic infections are established in an unknown number of patients. All those characteristics justify the pursuit of a prophylactic vaccine against O. tsutsugamushi; however, despite continuous efforts to develop such a vaccine since World War II, the objective has not been attained. In this review, we discuss the history of vaccine development against Orientia to provide a clear picture of the challenges that we continue to face from the perspective of animal models and the immunological challenges posed by an intracellular bacterium that normally triggers a short-lived immune response. We finish with a proposal for development of an effective and safe vaccine for scrub typhus through a new approach with a strong focus on T cell-mediated immunity, empirical testing of the immunogenicity of proteins encoded by conserved genes, and assessment of protection in relevant animal models that truly mimic human scrub typhus.