I just checked: Djerba was really cheap, around 17 Euros. Algiers was not too expensive either, 75 Euros all together. This was for airway fees and the bus to the terminal, landing was free! But as has been said, these things change quickly.
Fuel prices were at an all time high at the time. We paid less than two Euros per liter of Avgas in DAAG what was rather good. No Avgas in Djerba and I don’t know about Jet A.
I just want to say thank you all for all the helpful answers. Will update my trip here, so others can find new information here. So far I contacted White Rose Aviation, they look really helpful and willing to do more flights in one country for one fee, which sounds nice to me, because I plan to visit multiple airports in each country. I am also working on my time plans right now. Again, if you want to do Algerian / Tunisian meetup, let’s do it :) :-) About the fuel – I checked it multiple times and it seems big problem to get anything else than JET A, so I decided to take DA40, which runs on it. Avgas looks nearly impossible to get. Also their JET A is sometimes without antifreeze components. @AeroPlus – thanks as well, I just purchased your book, will read it during weekend time. @terbang – please, do you recall how much was average landing fees? Your trip looks incredible, my plan is similar, but little smaller :-)
Thank you very much for your kind answers.
I have contacted Swissport in Constantine (DABC) since that is my first planned stop. I have asked for parking, fuel and flight permits. I plan to use a Permis d’escale as Visa. If they can’t help me with the paperwork or their fees are too expensive, I will use the contacts provided in the AIP. My french is limited but I think it will be enough.
Wish me good luck, I will keep you updated.
Speed
It is not overly complicated to get the clearances for most countries in Africa if you can get your hands on the AIP documentation, the right contacts and can establish communication with them. Sometimes, it can be a better option to use a clearance office like GASE or White Rose Aviation. There are more of these companies based in Asia and Africa. Handling is also something that is not needed most of the time and if you do get handling, you will find that it includes nothing more than just a guy that walks with you from one office to the next to deal with all the paperwork. In some cases, it pays off to do the handling to save time.
I wrote a book about flying in or through Africa that discusses what all is involved in flying through the African continent which is also available as a Kindle ebook from Amazon.
I personally have by now been flying through most countries in Africa myself in a GA aircraft and enjoy it very much. There is a sense of adventure in it that can not be found with the flying in Europe. Prepare well, plan the fuel part carefully and then enjoy the trip!
Merged 
We did this tour in 2013, that included Algiers (DAAG) and Djerba, Tunesia (DTTJ):
We flew IFR, the information is quite old and our Mooney takes Avgas, so this might be of limited use for the OP, but anyway.
The AIP of Algeria is in fact French only, however, we were able to obtain the required permits with the info provided there in. We did not make use of any of the service providers. There was one number used for fax and phone. They insisted to have the application by fax but you had to call first so they could configure their device. It took us countless phone calls and being fluent in French was essential, both to organize the permits, as well as later in the country.
Tunesia was easier again. There are permits required as well, but the AIP is available in English and authorities were a bit more responsive. We could even explain to them, that Algeria was difficult and we had to be a bit flexible with the date of arrival.
Neither in Algiers nor in Djerba did we contract handling. We could not get contact to any agency in Algiers even though we tried. Everything took ages in DAAG but in the end we managed to refuel, get to the terminal and clear customs. Note that a visa is required to enter Algeria. We took the gamble and arrived without one and could enter on a permis d’escale.
In hindsight it might have been better to contract a handler in Djerba as it wouldn’t have been too expensive, reportedly around 50 Euros. Self handling was not a drama and people were friendly but it really took a long time to sort everything out, especially on departure.
Fees were reasonable in Algiers and quite cheap in Tunesia but these things change quickly. There is no Avgas in Djerba, reportedly the only place in Tunesia where it is available is Sfax, but we didn’t try. Fuel was really cheap in Algiers.
Ibra is correct, I went around Tunisia in a DA40/Jet-A in 2010. It was all pretty straightforward. Did Tunis, Tozeur, and Djerba. I’d have liked a bit more time in each spot in retrospect, as we only had one night in the latter two.
One interesting gotcha was that they would not allow us to bring a radio or GPS into the country, but it was fine if we left them airside in the airplane.
I have used White Rose for permits before, with good result, and also can strongly recommend General Aviation Support Egypt (GASE). They’re a very professional lot and the best value I’ve found.
Also as Ibra says, things may have changed in 8 years…!
172driver wrote:
If I can still find his email, I’ll PM it to you, lost contact with him.
Found his contact, but his email address is dead. Sorry.
Tunisia, I think katamarino did one in 2010 on a DA40/JetA? probably lot have changed in the country since 2011…
Algeria is a bit of no-mans land for GA even within French aeroclub circles, personally, I would try other easy places first (I bet many other places in Africa are much easier), in the other hand the VFR scenery is astonishing compared neighbours (have a look for book/film “Algeria From Above” by Yann Arthus-Bertrand)
