Over the course of several years, stars trace helical trajectories as they traverse across the sky due to the combined effects of proper motion and parallax. It is well known that the gravitational pull of an unseen companion can cause deviations to these tracks. Several studies have pointed out that the astrometric mission Gaia will be able to identify a slew of new exoplanets, stellar binaries, and compact object companions with orbital periods as short as tens of days to as long as Gaia's lifetime. Here, we use mock astrometric observations to demonstrate that Gaia can identify and characterize black hole companions to luminous stars with orbital periods longer than Gaia's lifetime. Such astrometric binaries have orbital periods too long to exhibit complete orbits, and instead are identified through curvature in their characteristic helical paths. By simultaneously measuring the radius of this curvature and the orbital velocity, constraints can be placed on the underlying orbit. We quantify the precision with which Gaia can measure orbital accelerations and apply that to model predictions for the population of black holes orbiting stars in the stellar neighborhood. Although orbital degeneracies imply that many of the accelerations induced by hidden black holes could also be explained by faint low-mass stars, we discuss how the nature of certain putative black hole companions can be confirmed with high confidence using Gaia data alone.