"I am an Tunisian national on J1 Visa in the US. However, I have never paid taxes in Tunisia. I did my PhD and was working in France for 5 years paying taxes there. I got my visa in france. Is my tax residency France or is it Tunisian?"--->This is US tax forum ; I guess you need to get professinal help from either a French/ Tunisian tax pro on your tax residency.
"Because if I claim it to be Tunisia, there is no two years tax treaty. If it's France, what documents I need to claim the tax refund?"--->I see; as said please contact a French/ Tunisian tax preparer for sure, Ok???
For tax treaty between US and France, please visit the IRS Website here:
http://www.irs.gov/pub/irs-trty/france.pdf