Massive stars at redshifts z > 6 are predicted to have played a pivotal role in cosmological reionization as luminous sources of ultra-violet (UV) photons. However, the remnants of these massive stars could be equally important as X-ray luminous (L_X 1e38 erg/s) high-mass X-ray binaries (HMXBs). Because the absorption cross section of neutral hydrogen decreases sharply with photon energy (proportional to the inverse cube), X-rays can escape more freely than UV photons from the star-forming regions in which they are produced, allowing HMXBs to make a potentially significant contribution to the ionizing X-ray background during reionization. In this paper, we explore the ionizing power of HMXBs at redshifts z > 6 using a Monte Carlo model for a coeval stellar population of main sequence stars and HMXBs. Using the archetypal Galactic HMXB Cygnus X-1 as our template, we propose a composite HMXB spectral energy distribution consisting of black-body and power-law components, whose contributions depend on the accretion state of the system. We determine the time-dependent ionizing power of a combined population of UV-luminous stars and X-ray luminous HMXBs, and deduce fitting formulae for the boost in the populations ionizing power arising from HMXBs; these fits allow for simple implementation of HMXB feedback in numerical simulations. Based on this analysis, we estimate the contribution of high redshift HMXBs to the present-day soft X-ray background, and we show that it is a factor of ~100-1000 smaller than the observed limit. Finally, we discuss the implications of our results for the role of HMXBs in reionization and in high redshift galaxy formation.