Improving the affinity of protein-protein interactions is a challenging problem that is particularly important in the development of antibodies for diagnostic and clinical use. Here, we used structure-based computational methods to optimize the binding affinity of VHNAC1, a single-domain intracellular antibody (intrabody) from the camelid family that was selected for its specific binding to the nonamyloid component (NAC) of human α-synuclein (α-syn), a natively disordered protein, implicated in the pathogenesis of Parkinson's disease (PD) and related neurological disorders. Specifically, we performed ab initio modeling that revealed several possible modes of VHNAC1 binding to the NAC region of α-syn as well as mutations that potentially enhance the affinity between these interacting proteins. While our initial design strategy did not lead to improved affinity, it ultimately guided us towards a model that aligned more closely with experimental observations, revealing a key residue on the paratope and the participation of H4 loop residues in binding, as well as confirming the importance of electrostatic interactions. The binding activity of the best intrabody mutant, which involved just a single amino acid mutation compared to parental VHNAC1, was significantly enhanced primarily through a large increase in association rate. Our results indicate that structure-based computational design can be used to successfully improve the affinity of antibodies against natively disordered and weakly immunogenic antigens such as α-syn, even in cases such as ours where crystal structures are unavailable.