Young stars and planets both grow by accreting material from the proto-stellar disks. Planetary structure and formation models assume a common origin of the building blocks, yet, thus far, there is no direct observational evidence correlating the composition of rocky planets to their host stars. Here we present evidence of a tight chemical link between rocky planets and their host stars. The iron-mass fraction of the most precisely characterized rocky planets is compared to that of their building blocks, as inferred from the atmospheric composition of their host stars. We find a clear and statistically significant correlation between the two. Our results explain the deviations from the Earth-like densities of planets which have been previously considered as anomalous. We also find that on average the iron-mass fraction of planets is higher than that of the primordial iron content in the planet building blocks, owing to the disk-chemistry and planet formation processes. Finally, our results provide some hints that the giant impact alone is not responsible for the high-densities of super-Mercuries. We conclude that rocky planet composition depends on the chemical composition of the proto-planetary disk and contains signatures about planet formation processes.