The MiniBooNE Collaboration reports first results of a search for $\nu_e$ appearance in a $\nu_\mu$ beam. With two largely independent analyses, we observe no significant excess of events above background for reconstructed neutrino energies above 475 MeV. The data are consistent with no oscillations within a two neutrino appearance-only oscillation model.