Structural studies of a ternary complex composed of the Yersina pestis virulence factors YopN, SycN and YscB were initially hampered by poor solubility of the individual proteins. Co-expression of all three proteins in Escherichia coli yielded a well behaved complex, but this sample proved to be recalcitrant to crystallization. As crystallization efforts remained fruitless, even after the proteolysis-guided engineering of a truncated YopN polypeptide, reductive methylation of lysine residues was employed to alter the surface properties of the complex. The methylated complex yielded crystals that diffracted X-rays to a maximal resolution of 1.8 A. The potential utility of reductive methylation as a remedial strategy for high-throughput structural biology was further underscored by the successful modification of a selenomethionine-substituted sample.