The association of branched polyethyleneimine (PEI) with a series of octacarboxy-calixresorcinarenes bearing different low-rim substituents leads to the formation of nanosized supramolecular complexes. The PEI-macrocycle complexes have fine-tunable sizes regulated by variations in the self-association capacity of the calixresorcinarenes. In the supramolecular complexes, hydrophobic fragments of the polymer and calixresorcinarenes form cooperative hydrophobic domains which provide synergistic enhancement of guest molecule binding. The formation of the supramolecular complexes was investigated by NMR FT-PGSE, NMR 2D NOESY, DLS and TEM methods. In addition, fluorimetry and UV-vis methods were used with the help of optical probes, namely water-soluble Crystal Violet and water-insoluble Orange OT. The investigation demonstrates the first example of the formation of cooperative hydrophobic domains in supramolecular polyelectrolyte-macrocycle complexes which enhance the binding of both water-soluble and water-insoluble organic compounds. The presented supramolecular systems have potential as sensory and drug delivery systems.