The influence of added surfactants on physical properties of associating polymer solutions was examined by a new statistical-mechanical theory of associating polymer solutions with multiple junctions and by computer simulation. The sol-gel transition line, the spinodal line, and the number of elastically effective chains in the mixed networks were calculated as functions of the concentration of added surfactants. All of them exhibited nonmonotonic behavior as a result of the following two competing mechanisms. One was the formation of new mixed micelles by binding surfactants onto the polymer associative groups. These micelles serve as crosslink junctions and promote gelation. The other was the replacement of polymer associative groups in the already formed network junctions by added surfactants. Such replacement lowers connectivity of junctions and destroys networks. The critical micelle concentration was also calculated. The results are compared with the reported experimental data on poly(ethylene oxide)-based associating polymers and hydrophobically modified cellulose derivatives. (C) 2004 Wiley Periodicals, Inc.