“Fluorescence-Activating and absorption-Shifting Tag” (FAST) is a well-studied fluorogen-activating protein with high brightness and low size, able to activate a wide range of fluorogens. This makes FAST a promising target for both protein and fluorogen optimization. Here, we describe the structure-based rational design of the enhanced FAST mutants, optimized for the N871b fluorogen. Using the spatial structure of the FAST/N871b complex, NMR relaxation analysis, and computer simulations, we identify the mobile regions in the complex and suggest mutations that could stabilize both the protein and the ligand. Two of our mutants appear brighter than the wild-type FAST, and these mutants provide up to 35% enhancement for several other fluorogens of similar structure, both in vitro and in vivo. Analysis of the mutants by NMR reveals that brighter mutants demonstrate the highest stability and lowest length of intermolecular H-bonds. Computer simulations provide the structural basis for such stabilization.