Advances in the last several years have enhanced mechanistic understanding of Nef-induced CD4 and MHCI downregulation and have suggested a new paradigm for analyzing Nef function. In both of these cases, Nef acts by forming ternary complexes with significant contributions to stability imparted by non-canonical interactions. The mutational analyses and binding assays that have led to these conclusions are discussed. The recent progress has been dependent on conservative mutations and multi-protein binding assays. The poorly understood Nef functions of p21 activated protein kinase (PAK2) activation, enhancement of virion infectivity, and inhibition of immunoglobulin class switching are also likely to involve ternary complexes and non-canonical interactions. Hence, investigation of these latter Nef functions should benefit from a similar approach. Six historically used alanine substitutions for determining structure-function relationships of Nef are discussed. These are M20A, E62A/E63A/E64A/E65A (AAAA), P72A/P75A (AXXA), R106A, L164A/L165A, and D174A/D175A. Investigations of less-disruptive mutations in place of AAAA and AXXA have led to different interpretations of mechanism. Two recent examples of this alternate approach, F191I for studying PAK2 activation and D123E for the critical residue D123 are discussed. The implications of the new findings and the resulting new paradigm for Nef structure-function are discussed with respect to creating a map of Nef functions on the protein surface. We report the results of a PPI-Pred analysis for protein-protein interfaces. There are three predicted patches produced by the analysis which describe regions consistent with the currently known mutational analyses of Nef function.