While both X-ray emission and Sunyaev-Zeldovich (SZ) temperature fluctuations are generated by the warm-hot gas in dark matter halos, the two observables have different dependence on the underlying physical properties, including the gas distribution. A cross-correlation between the soft X-ray background (SXRB) and the SZ sky may allow an additional probe on the distribution of warm-hot gas at intermediate angular scales and redshifts complementing studies involving clustering within SXRB and SZ separately. Using a halo approach, we investigate this cross-correlation analytically. The two contributions are correlated mildly with a correlation coefficient of $sim0.3$, and this relatively low correlation presents a significant challenge for its detection. The correlation, at small angular scales, is affected by the presence of radiative cooling or preheating and provides a probe on the thermal history of the hot gas in dark halos. While the correlation remains undetectable with CMB data from the WMAP satellite and X-ray background data from existing catalogs, upcoming observations with CMB missions such as Planck, for the SZ side, and an improved X-ray map of the large scale structure, such as the one planned with DUET mission, may provide a first opportunity for a reliable detection of this cross-correlation.