Banach-Tarski theorem without axiom of choice
The Banach-Tarski theorem heavily uses non-measurable sets. It is consistent that without the axiom of choice all sets are measurable and therefore the theorem fails in such universe. The paradox, therefore, relies on this axiom.
It is worth noting, though, that the Hahn-Banach theorem is enough to prove it, and there is no need for the full power of the axiom of choice.
More information can be found through here:
Herrlich, H. Axiom of Choice. Lecture Notes in Mathematics, Springer, 2006.
Schechter, E. Handbook of Analysis and Its Foundations. Academic Press, 1997.
Directly from Wikipedia's page on the Paradox/Theorem
Unlike most theorems in geometry, this result depends in a critical way on the axiom of choice in set theory. This axiom allows for the construction of nonmeasurable sets, collections of points that do not have a volume in the ordinary sense and for their construction would require performing an uncountably infinite number of choices.
While I'm aware you did not ask for this I cannot resist to suggest that you have a look at Stan Wagon's book 'The Banach-Tarski Paradox', Cambridge University Press 1985.