Fomalhaut is a triple system, with all components widely separated (~1E5 au). Such widely separated binaries are thought to form during cluster dissolution, but that process is unlikely to form such a triple system. We explore an alternative scenario, where A and C form as a tighter binary from a single molecular cloud core (with semimajor axis ~1E4 au), and B is captured during cluster dispersal. We use N-body simulations augmented with the Galactic tidal forces to show that such a system naturally evolves into a Fomalhaut-like system in about half of cases, on a timescale compatible with the age of Fomalhaut. From initial non-interacting orbits, Galactic tides drive cycles in B's eccentricity that lead to a close encounter with C. After several close encounters, typically lasting tens of millions of years, one of the stars is ejected. The Fomalhaut-like case with both components at large separations is almost invariably a precursor to the ejection of one component, most commonly Fomalhaut C. By including circumstellar debris in a subset of the simulations, we also show that such an evolution usually does not disrupt the coherently eccentric debris disk around Fomalhaut A, and in some cases can even produce such a disk. We also find that the final eccentricity of the disk around A and the disk around C are correlated, which may indicate that the dynamics of the three stars stirred C's disk, explaining its unusual brightness. ; Comment: Accepted to MNRAS