The SITE Intelligence Group, an American based company that monitors trends within the global jihadist movement, said the video was produced by the Islamic State and the Levant. It was also been distributed on Twitter and jihadi forums.
On the video a man, who says he is a Canadian and identifies himself as "Abu Anwar al-Canadi," urges his Muslim countrymen to follow the example of Martin Couture-Rouleau.
The National Post identified the man as John Maguire, a former University of Ottawa student who converted to Islam and became radicalized before leaving Canada last year. The newspaper cited friends and family.
The 23-year-old is among dozens of Canadians under RCMP investigation after allegedly making their way to Syria.
Couture-Rouleau killed one soldier — warrant officer Patrice Vincent — and injured another when he ran them down with a car in St-Jean-sur-Richelieu, Que., in October.
The video also references Michael Zehaf Bibeau's October attack in which he killed an honour guard at the National War Memorial in Ottawa before being shot dead while storming Parliament Hill.
"O people of Canada, you are said to be an educated people," Abu Anwar says in clear English as the video begins.
"So what is preventing you from being able to put two and two together and understanding that operations such as that of brother Ahmed Rouleau of Montreal and the storming of Parliament Hill in Ottawa, are carried out in direct response to your participation in the coalition of nations waging war against the Muslim people?"
Standing in the ruins of an unidentified area, Abu Anwar warns Canadians that their country being part of the U.S.-led coalition fighting Islamic State will bring revenge attacks upon them.
It is not clear where or when the video was recorded.
The Canadian government deployed fighter jets and support personnel to the Middle East earlier this year to join other countries conducting air strikes to support Iraqi ground forces battling Islamic state militants in northern Iraq.
Abu Anwar is believed to use the Twitter name Yahya Maguire, with postings critical of the fighting in Syria, but has not written on the social media site since October 2012.
In the video, he speaks directly to Canadians who follow the Muslim faith, telling them to launch attacks against their fellow Canadians or leave the country.
"You either pack your bags, or you prepare your explosive devices," he said on the English language video that had Arabic subtitles.
"You either purchase your airline ticket, or you sharpen your knife."
The Harper government did not respond directly to the video's contents and did not confirm or deny its authenticity. The government urged Canadians to be on their guard.
"Terrorism remains a real and serious threat to Canadians, which is why we must remain vigilant," Public Safety Minister Steven Blaney said in a prepared statement.
"That is why we are taking part in the coalition that is currently conducting air strikes against ISIL, and supporting the security forces in Iraq in their fight against this terrorist scourge," Blaney added.
"It is also the reason that we are working very determinedly to strengthen the tools available to the police and intelligence community to better protect us."
The video posted Sunday wasn't the first to depict Canadians urging Muslims to take up arms against their own countrymen.
In July, a Northern Ontario man believed killed fighting in Syria in 2013 was seen in another propaganda video, calling on Canadians to join the conflict.
In September another ISIL video warned westerners including Canadians that they would not feel secure in their bedrooms
Canadian intelligence officials estimated earlier this year that 130 Canadian extremists have joined the conflicts in either Syria or Iraq.
But not all of them are joining ISIL.
Some, such as former Canadian Forces Cpl. Dillon Hillier, have gone to the region to take up arms against the Islamic state militants.
Hillier, who used to serve with the Princess Patricia’s Canadian Light Infantry, has been fighting alongside Kurdish forces in northern Iraq since late November as part of the private 1st North American Expeditionary Force.
Blaney has advised Canadian citizens to "avoid engaging in a combat activity abroad."
Also on HuffPost