The decarboxylation reaction of protocatechuate has been described as a bottleneck and a rate-limiting step in cis,cis-muconate (ccMA) bioproduction from renewable feedstocks such as sugar. Because sugars are already in high demand in the development of many bio-based products, our work focuses on improving protocatechuate decarboxylase (Pdc) activity and ccMA production in particular, from lignin-related aromatic compounds. We previously had transformed an Escherichia coli strain using aroY, which had been used as a protocatechuate decarboxylase encoding gene from Klebsiella pneumoniae subsp. pneumoniae A170-40, and inserted other required genes from Pseudomonas putida KT2440, to allow the production of ccMA from vanillin. This recombinant strain produced ccMA from vanillin, however the Pdc reaction step remained a bottleneck during incubation. In the current study, we identify a way to increase protocatechuate decarboxylase activity in E. coli through enzyme production involving both aroY and kpdB; the latter which encodes for the B subunit of 4-hydroxybenzoate decarboxylase. This permits expression of Pdc activity at a level approximately 14-fold greater than the strain with aroY only. The expression level of AroY increased, apparently as a function of the co-expression of AroY and KpdB. Our results also imply that ccMA may inhibit vanillate demethylation, a reaction step that is rate limiting for efficient ccMA production from lignin-related aromatic compounds, so even though ccMA production may be enhanced, other challenges to overcome vanilate demethylation inhibition still remain.