The Metz duo of goalkeeper Alexandre Oukidja, and attacking midfielder Farid Boulaya are the new faces in the team that is headlined by Manchester City forward Riyad Mahrez.
No player from the Algerian League 1 has been selected.
Algeria began their Afcon qualifying campaign with a 1-0 home win over Togo.
Making it to Cameroon 2019 is not on top of their agenda but winning the tournament.
Failure to qualify for the 2018 Fifa World Cup and the group stage exit from the 2017 Afcon finals has mounted pressure on new coach Belmadi.
But Belmadi has not rung much changes in the team, investing trust in players who are already in the system like Nottingham Forest’s Hilal Soudani, goalkeeper Rais Mbolhi as well as forwards Islam Slimani and Yacine Brahimi.
Tunisia new coach Faouzi Benzarti has also taken the same approach of not tampering the squad he inherited in July.
Benzarti’s squad is dominated by players who were at the World Cup in Russia as Tunisia prepare to host Swaziland.
Striker Issam Jebali of Norwegian side Rosenborg, Kortrijk midfielder Larry Azouni and Karim Laaribi of Hellas Verona have been included, although they did not play in their previous call-ups.
Tunisia beat Egypt 1-0 in their opening match at home.
Mbolhi Rais (Al-Ettifak, Saudi Arabia), Oukdja Alexandre (Metz, France), Doukha Izzedine (Al-Raed, Saudi Arabia), Mandi Aissa (Real Betis, Spain), Bensebaini Ramy (Reennes, France), Slimani Islam (Fenerbahçe, Turkey), Feghouli Sofiane (Galatasaray, Turkey), Bentaleb Nabil (Schalk 04, Germany), Taider Saphir (Impact Montreal, Canada), Guedioura Adlane (Nottingham Forest, England), Mahrez Riyad (Manchester City, England), Soudani Hilal (Nottingham Forest, England), Ghezzal Rachid (Leicester City, England), Abeid Mehdi (Dijon, France), Boudebouz Ryad (Real Betis, Spain) Brahimi Yacine (Porto, Portugal), Bounedjah Baghdad (Al Sadd, Qatar), Boulaya Farid (Metz, France), Benzia Yassine (Lille, France), Fares Mohamed Salim (Spal, Italy), Haluche Rafik (Moreirense, Portugal), Jean Mehditahrat (Lens, France), Adellaoui Ayoub (Sion, Switzerland), Belkhither Mokhtar (Club Africain, Tunisia), Hassani Ilyes (Varna, Bulgaria)
Goalkeepers: Gaith Yeferni (US Ben Guerdane), Moez Ben Chrifia( Espérance de Tunis, Tunisia), Farouk Ben Mustapha (Al Shabab, Saudi Arabia)
Defenders: Hamdi Naguez (Zamalec SC, Egypt), Rami Bedoui (Etoile du Sahel, Tunisia), Siyam Ben Youssef (SK Kasimpasa, Turkey), Yassine Meriah (Olympiakos, Greece), Jasser Khemiri (Stade Tunisien, Tunisia), Oussema Haddadi (Dijon,France), Ali Maaloul (Al Ahly, Egypt), Hamza Mathlouthi (Sfaxien, Tunisia)
Midfielders: Ellyes Skhiri (Montpellier SC, France), Mohamed Amine Ben Amor (Etoile du Sahel, Tunisia), Anice Badri (Esperance de Tunis, Tunisia), Karim Laaribi (Hellas Verona, Italy), Ahmad Khalil (Club Afrcain, Tunisia), Larry Azouni (KV Kortrijk, Belgium)
Forwards: Fakhreddine Ben Youssef (Al Ettifaq FC, Saudi Arabia), Bassem Srarfi (Nice, France), Wahbi Khazri (Saint-Etienne, France), Naim Sliti (Dijon, France), Taha Yassine Khenissi (Esperance de Tunis, Tunisia), Issam Jebali (Rosenborg BK, Norway)