Samples of reliably identified halo wide binaries arc 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 neighbourhood, and is plagued by small number statistics at the widest separations. We present the results of a programme 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 per cent of candidate pairs up to 20 arcsec separation can be considered genuine halo wide binaries, to the limits of the available data. Precise parallaxes from 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 catalogues of halo wide binaries from upcoming large databases, e.g. Gaia and LSST.