The Sub-Electron-Noise Skipper CCD Experimental Instrument (SENSEI) uses the recently developed Skipper-CCD technology to search for electron recoils from the interaction of sub-GeV dark matter particles with electrons in silicon. We report first results from a prototype SENSEI detector, which collected 0.019 gram-days of commissioning data above ground at Fermi National Accelerator Laboratory. These commissioning data are sufficient to set new direct-detection constraints for dark matter particles with masses between ~500 keV and 4 MeV. Moreover, since these data were taken on the surface, they disfavor previously allowed strongly interacting dark matter particles with masses between ~500 keV and a few hundred MeV. We discuss the implications of these data for several dark matter candidates, including one model proposed to explain the anomalously large 21-cm signal observed by the EDGES Collaboration. SENSEI is the first experiment dedicated to the search for electron recoils from dark matter, and these results demonstrate the power of the Skipper-CCD technology for dark matter searches.