The burden of human infections with influenza A and B viruses is substantial, and the impact of influenza B virus infections can exceed that of influenza A virus infections in some seasons. Over the past few decades, viruses of two influenza B virus lineages (Victoria and Yamagata) have circulated in humans, and both lineages are now represented in influenza vaccines, as recommended by the World Health Organization. Influenza B virus vaccines for humans have been available for more than half a century, yet no systematic efforts have been undertaken to develop high-yield candidates. Therefore, we screened virus libraries possessing random mutations in the six “internal” influenza B viral RNA segments [i.e., those not encoding the major viral antigens, hemagglutinin (HA) and neuraminidase NA)] for mutants that confer efficient replication. Candidate viruses that supported high yield in cell culture were tested with the HA and NA genes of eight different viruses of the Victoria and Yamagata lineages. We identified combinations of mutations that increased the titers of candidate vaccine viruses in mammalian cells used for human influenza vaccine virus propagation and in embryonated chicken eggs, the most common propagation system for influenza viruses. These influenza B virus vaccine backbones can be used for improved vaccine virus production