Context. Collisionless shock waves have long been considered to be among the most prolific particle accelerators in the universe. Shocks alter the plasma they propagate through, and often exhibit complex evolution across multiple scales. Interplanetary (IP) traveling shocks have been recorded in situ for over half a century and act as a natural laboratory for experimentally verifying various aspects of large-scale collisionless shocks. A fundamentally interesting problem in both heliophysics and astrophysics is the acceleration of electrons to relativistic energies (> 300 keV) by traveling shocks. Aims. The reason for an incomplete understanding of electron acceleration at IP shocks is due to scale-related challenges and a lack of instrumental capabilities. This Letter presents the first observations of field-aligned beams of relativistic electrons upstream of an IP shock, observed thanks to the instrumental capabilities of Solar Orbiter. This study presents the characteristics of the electron beams close to the source and contributes to the understanding of their acceleration mechanism. Methods. On 25 July 2022, Solar Orbiter encountered an IP shock at 0.98 AU. The shock was associated with an energetic storm particle event, which also featured upstream field-aligned relativistic electron beams observed 14 min prior to the actual shock crossing. The distance of the beam’s origin was investigated using a velocity dispersion analysis (VDA). Peak-intensity energy spectra were anaylzed and compared with those obtained from a semi-analytical fast-Fermi acceleration model. Results. By leveraging Solar Orbiter’s high temporal resolution Energetic Particle Detector (EPD), we successfully showcase an IP shock’s ability to accelerate relativistic electron beams. Our proposed acceleration mechanism offers an explanation for the observed electron beam and its characteristics, while we also explore the potential contributions of more complex mechanisms.