Multivalent structures displaying different instead of similar sugar units, namely heteroglycoclusters (hGCs), are stimulating the efforts of glycochemists for developing compounds with new biological properties. Here we report a four-step strategy to synthesize hexadecavalent hGCs displaying eight copies of αFuc and βGal. These compounds were tested for the binding to lectins LecA and LecB from Pseudomonas aeruginosa. While parent fucosylated (19) and galactosylated (20) homoclusters present nanomolar affinity with LecB and LecA, respectively, we observed that hGCs combining these sugars (11 and 13) maintain their binding potency with both lectins despite the presence of an unspecific sugar. The added multivalency is therefore not a barrier for efficient recognition by bacterial receptors and it opens the route for adding different sugars that can be selected for their immunomodulatory properties.