Cervical cancer results from cervical infection by human papillomaviruses (HPVs), especially HPV16. An effective vaccine against these HPVs is expected to have a dramatic impact on the incidence of this cancer and its precursor lesions. The leading candidate, a subunit prophylactic HPV virus-like particle (VLP) vaccine, can protect women from HPV infection. An alternative improved vaccine that avoids parenteral injection, that is efficient with a single dose, and that induces mucosal immunity might greatly facilitate vaccine implementation in different settings. In this study, we have constructed a new generation of recombinant Salmonella organisms that assemble HPV16 VLPs and induce high titers of neutralizing antibodies in mice after a single nasal or oral immunization with live bacteria. This was achieved through the expression of a HPV16 L1 capsid gene whose codon usage was optimized to fit with the most frequently used codons in Salmonella. Interestingly, the high immunogenicity of the new recombinant bacteria did not correlate with an increased expression of L1 VLPs but with a greater stability of the L1-expressing plasmid in vitro and in vivo in absence of antibiotic selection. Anti-HPV16 humoral and neutralizing responses were also observed with different Salmonella enterica serovar Typhimurium strains whose attenuating deletions have already been shown to be safe after oral vaccination of humans. Thus, our findings are a promising improvement toward a vaccine strain that could be tested in human volunteers.