Im Jahr 1968 wurden die ersten Kontakte zwischen Heuchelheim und Gémenos (Provence, Frankreich) geknüpft mit dem Ziel, eine Städtepartnerschaft einzugehen. In beiden Gemeinden bildeten sich Komitees zur Vorbereitung  der Verschwisterung. In Heuchelheim  resultierte daraus 1969 die Gründung des „Vereins zur Pflege Internationaler Beziehungen“.

Alt-Bürgermeister Otto Bepler war einer  der Motoren der Partnerschaft, die 1970 offiziell begründet wurde. Ziel der Partnerschaft mit einer französischen Gemeinde waren  gegenseitige Begegnungen und Kontakte  zwischen Jugendlichen, Familien, Vereinen und den gemeindlichen Institutionen um das vereinte Europa auch in den persönlichen Kontakten zu leben.

Im Jahr 1991 wurden die ersten Kontakte zu einer weiteren Partnergemeinde hergestellt: nach dem Fall des „Eisernen Vorhangs“ besuchte eine polnische Delegation aus Dobrzen Wielki, einer Groß-Gemeinde in Schlesien, Heuchelheim. 1992 erfolgte die offizielle Verschwisterung.

Zu beiden Partnergemeinden hält der VIB enge Verbindung; im Wechsel organisiert der Verein jährlich eine Reise entweder nach Frankreich oder nach Polen; in dem gleichen Rhythmus empfängt der Verein gemeinsam mit der Gemeinde Heuchelheim jährlich Gäste aus den Partnergemeinden.  Zusätzlich hat der Verein mehrmals Jugendfreizeiten in Zusammenarbeit mit der Gemeinde oder dem Sportverein durchgeführt oder unterstützt.

Dass die Gemeinde die Partnerschaft stark unterstützte und gestaltete, kam auch dadurch zum Ausdruck, dass der jeweilige Bürgermeister auch meist der 1.Vorsitzende des Vereins wurde. Auf Otto Bepler folgte Willi Marx als 1. Vorsitzender und wurde dann durch Helmut Fricke abgelöst. Seit 2015 hat nun Bürgermeister Lars-Burkhard Steinz den Vorsitz inne.