Intrinsically disordered proteins (IDPs) are abundant in cells and have central roles in protein-protein interaction networks. Interactions between the IDP Prothymosin alpha (ProTa) and the Neh2 domain of Nuclear factor erythroid 2-related factor 2 (Nrf2), with a common binding partner, Kelch-like ECH-associated protein 1(Keap1), are essential for regulating cellular response to oxidative stress. Misregulation of this pathway can lead to neurodegenerative diseases, premature aging and cancer. In order to understand the mechanisms these two disordered proteins employ to bind to Keap1, we performed extensive 0.5–1.0 microsecond atomistic molecular dynamics (MD) simulations and isothermal titration calorimetry experiments to investigate the structure/dynamics of free-state ProTa and Neh2 and their thermodynamics of bindings. The results show that in their free states, both ProTa and Neh2 have propensities to form bound-state-like ß-turn structures but to different extents. We also found that, for both proteins, residues outside the Keap1-binding motifs may play important roles in stabilizing the bound-state-like structures. Based on our findings, we propose that the binding of disordered ProTa and Neh2 to Keap1 occurs synergistically via preformed structural elements (PSEs) and coupled folding and binding, with a heavy bias towards PSEs, particularly for Neh2. Our results provide insights into the molecular mechanisms Neh2 and ProTa bind to Keap1, information that is useful for developing therapeutics to enhance the oxidative stress response.