Beginning as in OTL
In 1236, the Abdalwadid kingdom of Tlemcen was established in West Algeria. Soon after, in 1268, their competitors, the Marinids, came to power in NW Africa.
Following the Peace of Ostia 1565, the Rum-Seljuks had to give up Latium (to Florence) and the Marches, Algiers, Tunis and Sicily (to the Triple Monarchy of England-Castille-Portugal). The 1580s saw the biggest uprisings against European rule in Morocco and Algeria yet.
During 1599-1604, the Triple Monarchy of England-Castille-Portugal and France fought the Seljuks together in the Great Seljuk War. In the peace of Naples, the Seljuks had to give the Sinai to France and all of Algeria and Tunisia to the Triple Monarchy of England-Castille-Portugal. When the latter fell apart though, France used the opportunity to grab Algeria in 1629, where the Castillian rule wasn't firm enough yet. The occupation forces fled from Algeria went mostly to the new kingdom of Sicily.
In 1765, the Governors of Nouvelle France, Algeria, Caroline and Louisiane declared independence - until France would have a king again. Lacking a navy (because the mostly noble captains didn't want to fight for a republic and thus deserted), France couldn't take them back. In November 1771, French Royalists in Algeria even attempted a landing in South France, supported by the Spanish navy. The landing itself was successful, but the people didn't rise against the republic, and the landed troops were defeated. Many ships had to be abandoned.
During 1798-1800, the Conquest of Algeria by Italy took place, with silent support by the French republic.