Dislocations in crystals naturally break the symmetry of the bulk, introducing local atomic configurations with symmetries such as fivefold rings. But dislocations do not usually nucleate aperiodic structure along their length. Here we demonstrate the formation of extended binary quasicrystalline precipitates with Penrose-like random-tiling structures, beginning with chemical ordering within the pentagonal structure at cores of prismatic dislocations in Mg-Zn alloys. Atomic resolution observations indicate that icosahedral chains centered along [0001] pillars of Zn interstitial atoms are formed templated by the fivefold rings at dislocation cores. They subsequently form columns of rhombic and elongated hexagonal tiles parallel to the dislocation lines. Quasicrystalline precipitates are formed by random tiling of these rhombic and hexagonal tiles. Such precipitation may impact dislocation glide and alloy strength.