As the closest unicellular relatives of animals, choanoflagellates serve as useful model organisms for understanding the evolution of animal multicellularity. An important factor in animal evolution was the increasing ocean oxygen levels in the Precambrian, which are thought to have influenced the emergence of complex multicellular life. As a first step in addressing these conditions, we study here the response of the colony-forming choanoflagellate $Salpingoeca\; rosetta$ to oxygen gradients. Using a microfluidic device that allows spatio-temporal variations in oxygen concentrations, we report the discovery that $S.\; rosetta$ displays positive aerotaxis. Analysis of the spatial population distributions provides evidence for logarithmic sensing of oxygen, which enhances sensing in low oxygen neighborhoods. Analysis of search strategy models on the experimental colony trajectories finds that choanoflagellate aerotaxis is consistent with stochastic navigation, the statistics of which are captured using an effective continuous version based on classical run-and-tumble chemotaxis.