With Australia Telescope Compact Array observations, we detect a highly elongated Mpc-scale diffuse radio source on the eastern periphery of the Bullet cluster 1E0657-55.8, which we argue has the positional, spectral and polarimetric characteristics of a radio relic. This powerful relic (2.3+/-0.1 x 10^25 W Hz^-1) consists of a bright northern bulb and a faint linear tail. The bulb emits 94% of the observed radio flux and has the highest surface brightness of any known relic. Exactly coincident with the linear tail we find a sharp X-ray surface brightness edge in the deep Chandra image of the cluster -- a signature of a shock front in the hot intracluster medium (ICM), located on the opposite side of the cluster to the famous bow shock. This new example of an X-ray shock coincident with a relic further supports the hypothesis that shocks in the outer regions of clusters can form relics via diffusive shock (re-)acceleration. Intriguingly, our new relic suggests that seed electrons for reacceleration are coming from a local remnant of a radio galaxy, which we are lucky to catch before its complete disruption. If this scenario, in which a relic forms when a shock crosses a well-defined region of the ICM polluted with aged relativistic plasma -- as opposed to the usual assumption that seeds are uniformly mixed in the ICM -- is also the case for other relics, this may explain a number of peculiar properties of peripheral relics.