We present 4110 strong gravitational lens candidates, 3887 of which are new discoveries, selected from a sample of 5,837,154 luminous red galaxies (LRGs) observed with the Dark Energy Spectroscopic Instrument (DESI). Candidates are identified via the presence of background ionized oxygen [O ii] nebular emission lines in the foreground LRG spectra, which may originate from the lensing of higher-redshift star-forming galaxies. Using the measured foreground redshift, background redshift, and integrated flux of the background [O ii] doublet, we integrate over impact parameters to compute the probability that each candidate is a lens. We expect 53% of candidates to be true lenses with Einstein radii ranging from 0 .″ 1–4″, which can be confirmed with high-resolution imaging. Confirmed strong lenses from this sample will form a valuable cosmological data set, as strong gravitational lensing is the only method to directly measure dark matter halo substructure at cosmological distances....