The mycobacterial PQS dioxygenase AqdC, a cofactor-less protein with an α/β-hydrolase fold, inactivates the virulence-associated quorum-sensing signal molecule 2-heptyl-3-hydroxy-4(1H)-quinolone (PQS) produced by the opportunistic pathogen Pseudomonas aeruginosa and is therefore a potential anti-virulence tool. We have used computational library design to predict stabilizing amino acid replacements in AqdC. While 57 out of 91 tested single substitutions throughout the protein led to stabilization, as judged by increases in (Formula presented.) of >2 °C, they all impaired catalytic activity. Combining substitutions, the proteins AqdC-G40K-A134L-G220D-Y238W and AqdC-G40K-G220D-Y238W showed extended half-lives and the best trade-off between stability and activity, with increases in (Formula presented.) of 11.8 and 6.1 °C and relative activities of 22 and 72 %, respectively, compared to AqdC. Molecular dynamics simulations and principal component analysis suggested that stabilized proteins are less flexible than AqdC, and the loss of catalytic activity likely correlates with an inability to effectively open the entrance to the active site.