  In this paper, we explore the establishment and evolution of the empirical
correlation between black hole mass and velocity dispersion with redshift. We
track the growth and accretion history of massive black holes starting from
high redshift using two seeding models:(i) Population III remnants, and (ii)
massive seeds from direct gas collapse. Although the seeds do not initially
satisfy the $M_{\rm BH} - \sigma$ relation, the correlation is established and
maintained at all times if self-regulating accretion episodes are associated
with major mergers. The massive end of the $M_{\rm BH} - \sigma$ relation is
established early, and lower mass MBHs migrate over time. How MBHs migrate
toward the relation, the slope and the scatter of the relation all depend
critically on the seeding model as well as the adopted self-regulation
prescription. We expect flux limited AGN surveys and LISA to select accreting
and merging MBHs respectively that have already migrated onto the $\msigma$
relation. This is a consequence of major mergers being more common at high
redshift for the most massive, biased, galaxies that anchor the $\msigma$
relation early. We also predict the existence of a large population of low mass
`hidden' MBHs at high redshift which can easily escape detection. Additionally,
we find that if MBH seeds are massive, $\sim 10^5 M_{\odot}$, the low-mass end
of the $\msigma$ flattens towards this asymptotic value, creating a
characteristic `plume'.
