We report the first measurement of the target-normal single-spin asymmetry in deep-inelastic scattering from the inclusive reaction $^3$He$^{\uparrow}\left(e,e' \right)X$ on a polarized $^3$He gas target. Assuming time-reversal invariance, this asymmetry is strictly zero in the Born approximation but can be non-zero if two-photon-exchange contributions are included. The experiment, conducted at Jefferson Lab using a 5.89 GeV electron beam, covers a range of $1.7 < W < 2.9$ GeV, $1.02$ GeV, which is non-zero at the $2.89\sigma$ level. Our measured asymmetry agrees both in sign and magnitude with a two-photon-exchange model prediction that uses input from the Sivers transverse momentum distribution obtained from semi-inclusive deep-inelastic scattering. Comment: This is the final edited version as published in PRL