Vesicles composed of an anionic and a cationic surfactant, with a net negative charge, associate strongly with a hydrophobically modified polycation (LM200) and with an unmodified polycation with higher charge density (JR400), forming viscoelastic gel-like structures. Calorimetric results show that in these gels, LM200 induces a rise of the chain melting temperature (T-m) of the vesicles, whereas JR400 has the opposite effect. For both polymer-vesicle systems, the shear viscosity exhibits an inflection point at T-m, and for the LM200 system the measured relaxation times are significantly higher below T-m. The neat vesicles and the polycation-bound vesicles have a polygonal-like faceted shape when the surfactant chains in the bilayer are crystallized, as probed by cryo-transmission electron microscopy. Above T-m, the neat and the LM200-bound vesicles regain a spheroidal shape, whereas those in the JR400 system remain with a deformed faceted shape even above T-m. These shape changes are interpreted in terms of different mechanisms for the polymer-vesicle interaction, which seem to be highly dependent on polymer architecture, namely charge density and hydrophobic modification. A crystallization-segregation mechanism is proposed for the LM200-vesicle system, while, for the JR400-vesicle one, charge polarization-lateral segregation effects induced by the polycation in the catanionic bilayer are envisaged.