El [[17 de octubre]] de [[1987]], cuando Homolka quien en ese entonces contaba contenía 17 años, conoció a [[Paul Bernardo]] de 23 años, en un restaurante de Scarborough. Una hora después, estaban juntos en la cama. El [[24 de diciembre]] de [[1989]], Bernardo le propuso matrimonio, momento que Homolka consideró como "el más romántico de su vida". La relación se rompió en [[1993]] cuando Homolka se [[divorcio|divorció]] de Bernardo y comenzó a declarar en su contra. Los llamaban "los asesinos del Niagara" o "Barbie y Ken".