Observations of the warm-hot (T > 105 K) phase of the intergalactic medium provide an important test of our understanding of galaxy evolution and help to verify our general cosmological paradigm. Simulations of structure growth predict that a substantial portion of baryons are shock heated to form the elusive warm-hot intergalactic medium (WHIM); however, with current facilities, very few blazars and AGN are bright enough to probe the WHIM in X-ray absorption. The luminous blazar 1ES 1553+113 provides a unique opportunity to study the WHIM in X-ray absorption over a large redshift pathlength due to investment of 1.8 megaseconds of XMM grating spectroscopy. Despite numerous attempts with large telescopes across the electromagnetic spectrum, observers have been unable to directly constrain the redshift of 1ES 1553+113, limiting the utility of the archival X-ray spectra. Here, we present the near-UV (NUV) spectrum of 1ES 1553+113 obtained by the Cosmic Origins Spectrograph (COS) on HST and perform a blind search for absorption lines to indirectly constrain its redshift. We find that the Lyα forest does not extend past z = 0.413. To infer a redshift constraint from this, we carry out a robust characterization of the highest-redshift intervening and associated HI Lyα lines (max(zLyα)) in the high-quality COS FUV spectra of 132 AGN with accurate spectroscopic emission redshifts (zem). We use the observed cumulative distribution of zem - max(zLyα) to measure an updated 95% confidence interval for the redshift of 1ES 1553+113 based purely on the edge of the observed Lyα forest of 0.408 < z < 0.438 (0.419 < z < 0.459) when using both intervening and associated (only intervening) lines. This redshift constraint rules out a WHIM origin for the stronger X-ray absorber detected toward 1ES 1553+113, perhaps suggesting that the WHIM is not sufficiently metal enriched to be detected in O VII or O VIII with current facilities. Finally, we consider applications to other blazars with unknown redshifts, which may be useful for future X-ray missions and studies of the extragalactic background light.