For the first time, solitary waves (SWs) have been observed within short large-amplitude magnetic structures (SLAMS) upstream of the Earth's quasi-parallel bow shock. The SWs often occur as bipolar pulses in the electric field data and move parallel to the background magnetic field at velocities of v = 400--1200 km/s. They have peak-to-peak amplitudes in the parallel electric field of up to E'$parallel$ = 65 mV/m and parallel scale sizes of L$parallel$ ~ 10 λD. The bipolar solitary waves exhibit negative potential structures of ∣Φ$parallel$∣ = 0.4--2.2 V, i.e., eΦ$parallel$/kTe ~ 0.1. None of the theories commonly used to describe SWs adequately address these negative potential structures moving at velocities above the ion thermal speed in a weakly magnetized plasma.