Conversion of CO2 to value-added products presents an opportunity to reduce GHG emissions while generating revenue. Formate, which can be generated by the electrochemical reduction of CO2, has been proposed as a promising intermediate compound for microbial upgrading. Here we present progress towards improving the soil bacterium Cupriavidus necator H16, which is capable of growing on formate as its sole source of carbon and energy using the Calvin–Benson–Bassham (CBB) cycle, as a host for formate utilization. Using adaptive laboratory evolution, we generated several isolates that exhibited faster growth rates on formate. The genomes of these isolates were sequenced, and resulting mutations were systematically reintroduced by metabolic engineering, to identify those that improved growth. The metabolic impact of several mutations was investigated further using RNA-seq transcriptomics. We found that deletion of a transcriptional regulator implicated in quorum sensing, PhcA, reduced expression of several operons and led to improved growth on formate. Growth was also improved by deleting large genomic regions present on the extrachromosomal megaplasmid pHG1, particularly two hydrogenase operons and the megaplasmid CBB operon, one of two copies present in the genome. Based on these findings, we generated a rationally engineered ΔphcA and megaplasmid-deficient strain that exhibited a 24% faster maximum growth rate on formate. Moreover, this strain achieved a 7% growth rate improvement on succinate and a 19% increase on fructose, demonstrating the broad utility of microbial genome reduction. This strain has the potential to serve as an improved microbial chassis for biological conversion of formate to value-added products.