The Cantor-Schroeder-Bernstein theorem (that if each of two sets admits an one-to-one map into the other then there is a bijection between them) is often proved using the axiom of choice. That proof uses the well-ordering theorem to assign to every set $X$, as its cardinal number, the smallest ordinal number in one-to-one correspondence with $X$. The hypothesis of the C-S-B theorem easily gives that the cardinal numbers of the two sets are each less than or equal to the other, and therefore equal. But there is another proof that entirely avoids the axiom of choice.

(Tangential remark: Using the well-ordering theorem to define cardinal numbers as above, one also gets an easy proof that, of any two sets, at least one admits a one-to-one map into the other. This conclusion is actually equivalent to the axiom of choice in the presence of the other ZF axioms.)

Tarski proved that, for any set $A$, the set $W(A)$ of well-orderable subsets of $A$ has strictly larger cardinality than $A$. This is trivial with AC, as then $W(A)$ is the whole power set of $A$ and thus Cantor's theorem applies. But Tarski gave a proof that avoids AC.

I don't have my copy of Howard and Rubin's "Consequences of the Axiom of Choice" handy, but if I did then I could probably find lots of examples by looking at the various forms numbered 0A, 0B, etc. I believe all of these are provable without AC (hence the number 0) but there was once a reason to suspect AC was needed.