The visit came a half-century after French forces brutally cracked down on independence fighters in a 1954-1962 war that left some 1.5 million Algerians dead.
French President Emmanuel Macron has made his first official visit to Algeria, announcing his arrival as a "friend" despite France's historically prickly relationship with its former colony.
Macron arrived in Algiers Wednesday, stressing that he had come as "a friend of Algeria, a constructive partner who wants to strengthen our links."
He held a one-hour meeting with President Abdelaziz Bouteflika, 80, who rarely appears in public after suffering a stroke in 2013 that affected his speech and mobility.
"I know the history, but I am not a hostage of the past," he told Algerian newspapers El Watan and El Khabar by phone ahead of his trip. "But from now on, I hope... that we will turn together towards the future."
With a few symbolic gestures, the French president tried to demonstrate his good will. He laid a wreath at a monument in central Algiers to those killed in the war, and walked through the center of the capital, talking with passersby.
He also told news website Tout sur l'Algerie that he was "ready" to see his country hand back the skulls of Algerian resistance fighters killed in the 1850s, which are held at the Musee de l'Homme in Paris.
Algerian and French academics have long campaigned for the return of the 37 skulls, a symbolic hangover from France's 130-year occupation of Algeria.
However, the visit was mostly aimed at developing France's economic ties with the former colony. Macron was accompanied by business executives including Xavier Niel, a telecommunications magnate who ranks first among the most influential French businessmen, according to Vanity Fair, and 129th wealthiest man in the world, according to Forbes.
In his interview with Algerian newspapers, he said: "Algeria must open up more; there are still many obstacles to investment."
During his election campaign in May, the French leader called his country's colonial history a "crime against humanity."
But in an interview with Le Point a year ago, he declared: "Sure, in Algeria, there was torture, but also surged a State, wealth, a middle class — that is the reality of colonization."
In a recent trip to west Africa, Macon also called for "neither denial nor repentance," stressing that "we cannot remain trapped in the past."