Self-healing rubber mixtures are described, the cross-linking of which is based on both ionic cluster formation and supramolecular association. For this, brominated poly(isobutylene-co-isoprene) rubber (BIIR) was converted with modifiers which contained one uracil and one imidazole moiety. The reaction with the imidazole moiety resulted in the formation of ionic groups which associated to ionic clusters. Additionally, supramolecular association of the uracil groups with a bifunctional (bi-) linker containing two diamidopyridyl moieties contributed to physical cross-linking of the rubber via triple hydrogen bonding. Mechanical properties including self-healing of the rubber mixtures are discussed in terms of competing interactions and a softening effect caused by the bi-linker. The results are supported by DMA measurements and low-field multiple-quantum (MQ) NMR experiments which delivered information about the macroscopic properties and the underlying molecular dynamics, respectively. The reversible nature of the network formation and the softening effect of the bifunctional linker enable multiple reprocessing without sacrificing mechanical performance, which is an important feature that distinguishes the rubber mixtures significantly from covalently cross-linked rubbers.