Although the study of X-ray binaries has led to major breakthroughs in high-energy astrophysics, their circumbinary environment at scales of ∼100–10,000 au has not been thoroughly investigated. In this paper, we undertake a novel and exploratory study by employing direct and high-contrast imaging techniques on a sample of X-ray binaries, using adaptive optics and the vortex coronagraph on Keck/NIRC2. High-contrast imaging opens up the possibility to search for exoplanets, brown dwarfs, circumbinary companion stars, and protoplanetary disks in these extreme systems. Here we present the first near-infrared high-contrast images of 13 high-mass X-ray binaries located within ∼2–3 kpc. The key results of this campaign involve the discovery of several candidate circumbinary companions ranging from substellar (brown dwarf) to stellar masses. By conducting an analysis based on Galactic population models, we discriminate sources that are likely background/foreground stars and isolate those that have a high probability (≳60%–99%) of being gravitationally bound to the X-ray binary. This paper seeks to establish a preliminary catalog for future analyses of proper motion and subsequent observations. With our preliminary results, we calculate the first estimate of the companion frequency and the multiplicity frequency for X-ray binaries: ≈0.6 and 1.8 ± 0.9, respectively, considering only the sources that are most likely bound to the X-ray binary. In addition to extending our comprehension of how brown dwarfs and stars can form and survive in such extreme systems, our study opens a new window to our understanding of the formation of X-ray binaries.