In a TV interview in Algiers this week, the centrist said French actions in Algeria, which achieved independence in 1962 after eight years of war, were "genuinely barbaric, and constitute a part of our past that we have to confront by apologising".
His visit also included a stop at the Martyrs' Memorial in Algiers, saying he wanted to promote a "reconciliation of memories" between the two countries.
The violent history between France and Algeria is still a source of tension between the two countries and within French political circles.
Political parties in Algeria have long denounced the refusal of the French authorities to recognise and apologize for the crimes committed by colonial France in Algeria. And French governments over the years have often been accused of being in denial about the violence of its colonial rule, which reached a peak during the Algerian war of independence that ended in 1962.
President François Hollande has made moves in recent years to sooth relations, firstly recognizing the "bloody repression" of Algerian protesters by police in Paris in October 1961 and also for France's treatment of the Harkis - Algerians who had fought for France.
But on a visit to Algeria in 2012 Hollande stopped short of apologizing for France's colonial rule despite recognizing the French occupation was "brutal".
So Macron's suggestion that France must apologize, as expected, drew a stern reaction from his rivals on the right.
His rivals on the right for the French presidency -- due to be decided in a first round election in April and a run-off between the two top candidates in May -- pounced on the comments.
Les Republicans candidate Francois Fillon on Wednesday denounced what he called "this hatred of our history, this perpetual repentance that is unworthy of a candidate for the presidency of the republic".
Wallerand de Saint-Just, an official in Marine Le Pen's far-right National Front party, accused Macron of "shooting France in the back", while Gerald Darmanin, an ally of ex-president Nicolas Sarkozy, tweeted "Shame on Emmanuel Macron for insulting France while abroad".
It was the not the first time Macron, who currently leads the polls for the two rounds of voting in April and May, has touched on the livewire issue.
"Yes, there was torture in Algeria, but there was also the emergence of a state, or wealth, of a middle class," he told the magazine Le Point in October.
"This is the reality of colonialism. There are elements of civilisation and elements of barbarism."
'Colonialism was France sharing its culture'
And Fillon has been tripped up by his own comments on French colonialism.
In August, he drew claims of trying to sanitise history, claiming that "France is not guilty of having wanted to share its culture with the peoples of Africa".
Macron remains the frontrunner in the presidential race, with 39 percent of those surveyed in the latest survey by pollsters Ipsos giving him a favourable opinion.
In the poll released by the magazine Le Point on Wednesday, Macron was followed by Socialist candidate Benoit Hamon, with 38 percent, while Fillon tumbled 18 percentage points to 25 percent, just behind Le Pen, on 26 percent.