We mine the Tycho-Gaia astrometric solution (TGAS) catalogue for wide stellar binaries by matching positions, proper motions and astrometric parallaxes. We separate genuine binaries from unassociated stellar pairs through a Bayesian formulation that includes correlated uncertainties in the proper motions and parallaxes. Rather than relying on assumptions about the structure of the Galaxy, we calculate Bayesian priors and likelihoods based on the nature of Keplerian orbits and the TGAS catalogue itself. We calibrate our method using radial velocity measurements and obtain 7108 high-confidence candidate wide binaries with projected separations s<~1pc. The normalization of this distribution suggests that at least 0.7 per cent of TGAS stars have an associated, distant TGAS companion in a wide binary. We demonstrate that Gaia's astrometry is precise enough that it can detect projected orbital velocities in wide binaries with orbital periods as large as 10^6^yr. For pairs with s<~4x10^4^au, characterization of random alignments indicates our contamination to be 5-10 per cent. For s<~5x10^3^au, our distribution is consistent with Opik's law. At larger separations, the distribution is steeper and consistent with a power-law P(s){propto}s^-1.6^; there is no evidence in our data of any bimodality in this distribution for s<~1pc. Using radial velocities, we demonstrate that at large separations, i.e. of order s~1pc and beyond, any potential sample of genuine wide binaries in TGAS cannot be easily distinguished from ionized former wide binaries, moving groups or contamination from randomly aligned stars.