We report observations of "fast solitary waves" that are ubiquitous in downward current regions of the mid-altitude auroral zone. The single-period structures have large amplitudes (up to 2.5 V/m), travel much faster than the ion acoustic speed, carry substantial potentials (up to ∼100 Volts), and are associated with strong modulations of energetic electron fluxes. The amplitude and speed of the structures distinguishes them from ion-acoustic solitary waves or weak double layers. The electromagnetic signature appears to be that of an positive charge (electron hole) traveling anti-earthward. We present evidence that the structures are in or near regions of magnetic-field-aligned electric fields and propose that these nonlinear structures play a key role in supporting parallel electric fields in the downward current region of the auroral zone.