AuNi is a classic long-studied fcc alloy combining a very “large” atom (Au) and a very “small” atom (Ni), and the large atomic size misfits suggest very high strengthening. Here, AuNi is used as a model alloy for the testing of new strengthening theories in random alloys that include the effects of both size misfits and solute–solute interactions. Experimentally, AuNi samples are fabricated, characterized, and tested, and show no segregation after annealing at 900 °C and a very high yield strength of 769 MPa. Theoretically, the main inputs to the theory (alloy lattice and elastic constants, solute misfit volumes, energy fluctuations associated with slip in the presence of solute–solute interactions) are extracted from experiments or computed using first-principles DFT. The parameter-free prediction of the yield strength is 809 MPa, in very good agreement with experiments. Solute–solute interactions enhance the strength only moderately (13%), demonstrating that the strengthening is dominated by the solute misfit contribution. Various aspects of the full theory are discussed, the general methodology is presented in an easy-to-apply analytic framework, and a new analysis for strengthening in alloys with zero misfits but non-zero solute–solute interactions is presented. These results provide support for the theories and point toward applications to many fcc complex concentrated alloys.