Mathematicians have been using an intuitive concept of a set for probably as long as mathematics has been practiced. At first, mathematicians assumed that the axiom of choice was simply true (as indeed it is for finite collections of sets).
Georg Cantor introduced the concept of transfinite numbers and different cardinalities of infinity in a 1874 paper (which contains his infamous Diagonalization Argument) and along with this sparked the introduction of set theory. In 1883, Cantor introduced a principle called the 'Well-Ordering Princple' (discussed further in a section below) which he called a 'law of thought' (i.e., intuitively true). He attempted to prove this principle from his other principles, but found that he was unable to do so.
Ernst Zermelo attempted to develop an axiomatic treatment of set theory. He managed to prove the Well-Ordering Principle in 1904 by introducing a new principle: The Principle of Choice. This sparked much discussion amongst mathematicians. In 1908 published a paper containing responses to this debate, as well as a new formulation of the Axiom of Choice. In this year, he also published his first version of the set theoretic axioms, known as the Zermelo Axioms of Set Theory. Mathematicians, Abraham Fraenkel and Thoralf Skolem improved this system (independently of each other) into its modern version, the Zermelo Fraenkel Axioms of Set Theory.
In 1914, Felix Hausdorff proved Hausdorff's paradox. The ideas behind this proof were used in 1924 by Banach and Alfred Tarski to prove the more famous Banach-Tarski paradox (discussed in more detail below). This latter theorem is often quoted as evidence of the falsehood of the axiom of choice.
Between 1935 and 1938, Kurt Gödel proved that the Axiom of Choice is consistent with the rest of the ZF axioms.
Finally, in 1963, Paul Cohen developed a revolutionary mathematical technique called forcing, with which he proved that the axiom of choice could not be proven from the ZF axioms (in particular, that the negation of AC is consistent with ZF). For this, and his proof of the consistency of the negation of the Generalized Continuum Hypothesis from ZF, he was awarded a fields medal in 1966.
This axiom came to be accepted in the general mathematical community, but was rejected by the constructive mathematicians as being fundamentally non-constructive. However, it should be noted that in many forms of constructive mathematics, there are provable versions of the axiom of choice. The difference is that in general in constructive mathematics, exhibiting a set of non-empty sets (technically, in constructive set-theory, these should be 'inhabited' sets) also amounts to exhibiting a proof that they are all non-empty, which amounts to exhibiting an element for all of them, which amounts to exhibiting a function choosing an element in each. So in constructive mathematics, to even state that you have a set of inhabited sets requires stating that you have a choice function to these sets proving they are all inhabited.
Some explanation of the history of the axiom of choice (as well as some of its issues) can be found in the paper "100 years of Zermelo's axiom of choice: what was the problem with it?" by the constructive mathematician Per Martin-Löf at this webpage.
(Martin-Löf studied under Andrey Kolmogorov of Kolmogorov complexity and has made contributions to information theory, mathematical_statistics, and mathematical_logic, including developing a form of intuitionistic type theory).
A nice timeline is also summarised on Stanford Encyclopaedia of Philosophy.