This letter reports on the first observation of an octupole band in the neutron-deficient $(N=Z+2)$ nucleus $^{110}$Xe. The $^{110}$Xe nuclei were produced via the $^{54}$Fe($^{58}$Ni,2n) fusion-evaporation reaction. The emitted γ rays were detected using the jurogam 3 γ-ray spectrometer, while the fusion-evaporation residues were separated with the MARA separator at the Accelerator Laboratory of the University of Jyväskylä, Finland. The experimental observation of the low-lying 3$^{−}$ and 5$^{−}$ states and inter-band E1 transitions between the ground-state band and the octupole band proves the importance of octupole correlations in this region. These new experimental data combined with theoretical calculations using the symmetry-conserving configuration-mixing method, based on a Gogny energy density functional, have been interpreted as an evidence of enhanced octupole correlations in neutron-deficient xenon isotopes.