Maltose-binding protein (MBP) from Escherichia coli has been shown to be a good substrate for protein engineering leading to altered binding (Marvin and Hellinga, Proc Natl Acad Sci U S A 98: 4955-4960, 2001a) and increased affinity (Marvin and Hellinga, Nat Struct Biol 8: 795-798, 2001b; Telmer and Shilton, J Biol Chem 278: 34555-34567, 2003). It is also used in recombinant protein expression as both an affinity tag and a solubility tag. We isolated mutations in MBP that enhance binding to maltodextrins 1.3 to 15-fold, using random mutagenesis followed by screening for enhanced yield in a microplate-based affinity purification. We tested the mutations for their ability to enhance the yield of a fusion protein that binds poorly to immobilized amylose and their ability to enhance the solubility of one or more aggregation-prone recombinant proteins. We also measured dissociation constants of the mutant MBPs that retain the solubility-enhancing properties of MBP and combined two of the mutations to produce an MBP with a dissociation constant 10-fold tighter than wildtype MBP. Some of the mutations we obtained can be rationalized based on the previous work, while others indicate new ways in which the function of MBP can be modified.