Large-amplitude (up to ∼50 mV/m) solitary waves, identified as electron holes, have been observed during waveform captures on two of the four Cluster satellites during several plasma sheet encounters that have been identified as the passage of a magnetotail reconnection x line. The electron holes were seen near the outer edge of the plasma sheet, within and on the edge of a density cavity, at distances on the order of a few ion inertial lengths from the center of the current sheet. The electron holes occur during intervals when there were narrow electron beams but not when the distributions were more isotropic or contained beams that were broad in pitch angle. The region containing the narrow beams (and therefore the electron holes) can extend over thousands of kilometers in the x and y directions, but is very narrow in the z direction. The association with electron beams and the density cavity and the location along the separatrices are consistent with simulations shown herein. The velocities and scale sizes of the electron holes are consistent with the predictions of Drake et al. . Particle simulations of magnetic reconnection reproduce the observed Cluster data only with the addition of a small (0.2 of the reversed field) ambient guide field. The results suggest that electron holes may sometimes be an intrinsic feature of magnetotail reconnection and that in such cases the traditional neglect of the guide field may not be justified. Very large amplitude lower hybrid waves (hundreds of millivolts per meter), as well as waves at frequencies up to the electron plasma frequency, were also observed during this interval.