Samples of reliably identified halo wide binaries are scarce. If reasonably free from selection effects and with a small degree of contamination by chance alignments, these wide binaries become a powerful dynamical tool, having provided one of the very few experiments capable of constraining the nature of dark matter in the Milky Way halo. Currently, however, the best available sample of halo wide binaries is confined to the solar neighborhood, and is plagued by small number statistics at the widest separations. We present the results of a program aimed to probe the wide binary population of the Galactic halo at significantly larger distances, and which informs future searches that could improve the statistics by orders of magnitude. Halo stars were taken from the Sloan Digital Sky Survey after analysing the Galactic orbits of stars in the reduced proper motion diagram. We then select candidate binaries by searching for pairs with small differences in proper motion and small projected separation on the sky. Using medium-resolution spectroscopy, a subsample of candidates is validated via radial velocities, finding that about 68\% of candidate pairs up to 20$^{\prime\prime}$ separation can be considered genuine halo wide binaries, to the limits of the available data. Precise parallaxes from \textit{Gaia} confirm that most of our selected pairs have their components at the same distances, independently confirming the robustness of our selection method. These results should prove valuable to guide the optimal assembly of larger catalogs of halo wide binaries from upcoming large databases, e.g., \textit{Gaia} and LSST.