Det var ett åtagande som under Harpers nästan tio år som premiärminister hade sett Kanada, länge betraktat i regionen som en ärlig, om än mindre, mäklare i arabisk-israelisk konflikt, med eftertryck och otvetydig inriktning på den israeliska sidan.
Även om han utan tvivel kommer att förbli Israels vän, kommer den tillträdande premiärministern Justin Trudeau också att sträva efter att reparera förbindelserna med arabvärlden för att hävda sin fasta övertygelse att en tvåstatslösning kräver dialog med båda sidor.
Harper lyckades däremot ge intryck av att muslimer och araber inte skulle kunna lita på honom, och det är högst talande i hans hantering av den syriska flyktingkrisen.
Hans regering svarade under kampanjen mot treåriga Alan Kurdis drunknande död, som med sin syster och sina föräldrar försökte ansluta sig till familjen i Kanada, och betonade det svåra faktum att endast ett litet antal flyktingar har tillåtits komma in i landet.
I början av kampanjen åtog sig Trudeau Kanada att omedelbart ta med sig 25 000 flyktingar, och han fångade tydligt väljarnas sinnesstämning när han sade:
"Kanadensare får det, att detta handlar om att göra det rätta, det handlar om att leva upp till de värderingar som vi värnar om i detta land."
Och om det fanns en svängande stund i detta val, var det förmodligen en debatt i provinsen Quebec, på franska, om niqab (en ansiktsslöja).
Harper hade motsatt sig en ny kanadensisk medborgares önskan att bära sin niqab vid ceremonin och till och med föra fallet till Högsta domstolen, där han förlorade. Men han höll fast vid sin ståndpunkt att niqab hotade det kanadensiska samhället.
"De flesta kanadensare tror att det är kränkande att någon skulle dölja sitt ID just nu där de förbinder sig att gå med i den kanadensiska familjen," var hur han uttryckte det.
Trudeau argumenterade å andra sidan: "Det är uppenbart att han spelar mycket vårdslösa och farliga spel, ställer kanadensare mot varandra för ett snävt politiskt mål."
Trudeau ansåg också att Kanada borde dra tillbaka sina stridsflygplan från bombkampanjen mot den så kallade islamiska staten.
Men i en skicklig touch som visade att han inte är någon pacifist lovade han att engagera fler trupper för att utbilda irakiska och kurdiska markstyrkor för att bekämpa jihadisterna samtidigt som han kallade tid på Kanadas engagemang i flygkriget.
När det gäller Iran, där Harpers regering hade kallskuldrat kärnvapenavtalet och bekräftat sitt stöd för Israel, intog Trudeau återigen en nyanserad ståndpunkt, välkomnade ett "betydande avtal" och bekräftade "vikten av en diplomatisk lösning samtidigt som han såg till att Iran inte kan bygga ett kärnvapen".
I varje större Mellanösternfråga erbjöd Trudeau en ny tagning. Harper med sitt orubbliga stöd för Netanyahu och sin djupa misstänksamhet mot Iran och en stor del av arabvärlden förde inget nytt till bordet. Efter att ha bevakat sin ståndpunkt visade han sig oförmögen att flytta från den, en ödesdiger brist hos en väljarkår som hungrade efter förändring.
I själva verket är det ingen liten ironi att medan Mellanöstern i de TV-sända ledarnas debatter fick liten uppmärksamhet, på kampanjspåret kan det mycket väl ha visat sig vara Stephen Harpers häl.
Nu är flyktingkrisen den mest brådskande frågan och den som Trudeau kan agera snabbt på, när de konservativas verksamhet fortfarande är färsk.
Hur Kanadas nya premiärminister svarar kommer att vara en tydlig indikation på hur betydande en omläggning av Mellanösterns politik hans regering är beredd att göra.
Bill Law är en Mellanösternanalytiker och specialist på Gulffrågor. Följ honom @BillLaw49
När Stephen Harper slog ut de sista pianoackorden till Beatles sång Hey Jude vid en privat middag för Benjamin Netanyahu i Jerusalem förra året, betonade han, om än något bisarrt, sitt absoluta engagemang för den israeliska ledaren.