Using the UltraVISTA catalogs, we investigate the evolution in the 11.4~Gyr since $z=3$ of the progenitors of local ultra-massive galaxies ($\log{(M_{\rm star}/M_{\odot})}\approx11.8$; UMGs), providing a complete and consistent picture of how the most massive galaxies at $z=0$ have assembled. By selecting the progenitors with a semi-empirical approach using abundance matching, we infer a growth in stellar mass of 0.56$^{+0.35}_{-0.25}$ dex, 0.45$^{+0.16}_{-0.20}$~dex, and 0.27$^{+0.08}_{-0.12}$ dex from $z=3$, $z=2$, and $z=1$, respectively, to $z=0$. At $z<1$, the progenitors of UMGs constitute a homogeneous population of only quiescent galaxies with old stellar populations. At $z>1$, the contribution from star-forming galaxies progressively increases, with the progenitors at $2<z<3$ being dominated by massive ($M_{\rm star} \approx 2 \times 10^{11}$M$_{\odot}$), dusty ($A_{\rm V}\sim$1--2.2 mag), star-forming (SFR$\sim$100--400~M$_{\odot}$ yr$^{-1}$) galaxies with a large range in stellar ages. At $z=2.75$, $\sim$15\% of the progenitors are quiescent, with properties typical of post-starburst galaxies with little dust extinction and strong Balmer break, and showing a large scatter in color. Our findings indicate that at least half of the stellar content of local UMGs was assembled at $z>1$, whereas the remaining was assembled via merging from $z\sim 1$ to the present. Most of the quenching of the star-forming progenitors happened between $z=2.75$ and $z=1.25$, in good agreement with the typical formation redshift and scatter in age of $z=0$ UMGs as derived from their fossil records. The progenitors of local UMGs, including the star-forming ones, never lived on the blue cloud since $z=3$. We propose an alternative path for the formation of local UMGs that refines previously proposed pictures and that is fully consistent with our findings.