We study the properties of black holes and their host galaxies across cosmic time in the Illustris simulation. Illustris is a large scale cosmological hydrodynamical simulation which resolves a (106.5 Mpc)^3 volume with more than 12 billion resolution elements and includes state-of-the-art physical models relevant for galaxy formation. We find that the black hole mass density for redshifts z = 0 - 5 and the black hole mass function at z = 0 predicted by Illustris are in very good agreement with the most recent observational constraints. We show that the bolometric and hard X-ray luminosity functions of AGN at z = 0 and 1 reproduce observational data very well over the full dynamic range probed. Unless the bolometric corrections are largely underestimated, this requires radiative efficiencies to be on average low, epsilon_r <= 0.1, noting however that in our model radiative efficiencies are degenerate with black hole feedback efficiencies. Cosmic downsizing of the AGN population is in broad agreement with the findings from X-ray surveys, but we predict a larger number density of faint AGN at high redshifts than currently inferred. We also study black hole -- host galaxy scaling relations as a function of galaxy morphology, colour and specific star formation rate. We find that black holes and galaxies co-evolve at the massive end, but for low mass, blue and star-forming galaxies there is no tight relation with either their central black hole masses or the nuclear AGN activity.