We initiate the study of model theory in the absence of the Axiom of Choice, using the Axiom of Determinateness as a powerful substitute. We first show that, in this context, $\mathscr{L}_{\omega_1\omega}$ is no more powerful than first-order logic. The emphasis then turns to upward Lowenhein-Skolem theorems; $\aleph_1$ is the Hanf number of first-order logic, of $\mathscr{L}_{\omega_1\omega}$, and of a strong fragment of $\mathscr{L}_{\omega_1\omega}$. The main technical innovation is the development of iterated ultrapowers using infinite supports; this requires an application of infinite-exponent partition relations. All our theorems can be proven from hypotheses weaker than AD.