Polyketides are valuable natural products that have antibacterial, anticancer, and immunosuppressant activities. Many bacterial polyketides are produced by modular polyketide synthases (PKS) in an assembly line fashion from simple two-carbon monomer inputs. Two PKS pathways, encoding erythromycin and epothilone, have been heterologously expressed in Escherichia coli (E. coli), but at low yields (0.001-20mg/L). We aimed to improve E. coli as a host for polyketide production by providing more monomer inputs for PKS assembly lines. For many polyketides, the extender monomer is methylmalonyl-CoA and the enzyme that provides it is propionyl-CoA carboxylase (PCC). We used as our test system a strain of E. coli harboring the 6-deoxyerythronolide B synthase PKS, which produces the erythromycin polyketide. We designed and synthesized DNA encoding 20 PCC gene homologs from different species and built 20 versions of the E. coli polyketide-producing strain, each harboring a different PCC homolog. We observed variability in polyketide production amongst the 20 strains, and identified optimal PCC homologs. These results may be useful for improving E. coli as a host for heterologous expression of orphan PKSs, as well as for engineering polyketides and producing novel unnatural products.