The Deys of Algeria launched frequent attacks against the Beys of Tunisia to achieve autonomy in the region (see Tunisian-Algerian Wars).

[1] Eventually the eldest son, Muhammad, was able to ward off Algeria and was also able to avoid paying tribute on account that both countries were under Ottoman rule.

[2] This newfound prosperity would soon be challenged at the emergence of Hammuda ibn Ali and Algeria's disliking towards his desire to end the economic exploitation of Tunisia still occurring.

Contrast this with the bloody Algerian War of independence and the creation of a state that was headed by the National Liberation Front (Algeria) who was a decidedly socialist party.

Tunisia supported Algeria in their war of independence by letting members of the FLN use Tunisian towns as bases of operation, which eventually led to the bombing of the village of Sakiet Sidi Youssef.

[5] A rift between these two nations had begun to form however, as Tunisia was backed by the United States while Algeria was supportive of the Soviet Union.

[4] In 1987 the departure from power in Tunisia of President Habib Bourguiba and his replacement by the more diplomatic Zine el Abidine Ben Ali brought the two nations closer again.

[5] While addressing the Maghribi summit the day after signing the pact, leader of Tunisia at the time Zine El Abidine Ben Ali said this about the newly formed alliance, “This declaration in itself represents a core political choice whose features became clear on the agreement that defines the legal and institutional framework for unified Maghreb action.”[5] This pact was essential for both parties, It provided Tunisia a guarantee that Algerian hegemony in the region would not be realized while for Algeria it provided political stability and allowed them to regain support from the people after social unrest in 1988.

The Tunisian Revolution resulted in longtime President of Tunisia Zine El Abidine Ben Ali being overthrown when the Islamists represented by the Ennahda Movement took the reins of power in Carthage.

Algeria, who was relatively unaffected by the Arab Spring, has worked with the Tunisian government to create more security along the border while actively fighting terrorist groups in Tunisia.

The borders security originally relied on the deals made by former President Zine El Abidine Ben Ali with various groups.

[10] After his ousting, the power vacuum led to the unregulated trafficking of weapons, smuggling and taking control of border crossings by force.

As political tensions rise in the region, especially in Tunisia as more Tunisians do not recognize Kais Saied's government as legitimate, both of these countries have attempted to maintain good relations.

[17][18] In September 2022, Tunisia invited the leader of the Polisario Front to Tunis in order to discuss the current situation in Western Sahara.