Infections caused by Klebsiella pneumoniae are a major public health threat. Extensively drug-resistant and even pan-resistant strains have been reported. Understanding K. pneumoniae pathogenesis is hampered by the fact that murine models of infection offer limited resolution for non-hypervirulent strains which cause the majority of infections. The insect Galleria mellonella larva is a widely used alternative model organism for bacterial pathogens. We have performed genome-scale fitness profiling of a multidrug-resistant K. pneumoniae ST258 strain during infection of G. mellonella, to determine if this model is suitable for large-scale virulence factor discovery in this pathogen. Our results demonstrated a dominant role for surface polysaccharides in infection, with contributions from siderophores, cell envelope proteins, purine biosynthesis genes and additional genes of unknown function. Comparison with a hypervirulent strain, ATCC 43816, revealed substantial overlap in important infection-related genes, as well as additional putative virulence factors specific to ST258, reflecting strain-dependent fitness effects. Our analysis also identified a role for the metalloregulatory protein NfeR (YqjI) in virulence. Overall, this study offers new insight into the infection fitness landscape of K. pneumoniae, and provides a framework for using the highly flexible and easily scalable G. mellonella infection model to dissect molecular virulence mechanisms of bacterial pathogens.