This is the second of three papers that search for the predicted stellar cusp around the Milky Ways central black hole, Sagittarius A*, with new data and methods. We aim to infer the distribution of the faintest stellar population currently accessible through observations around Sagittarius A*. We use adaptive optics assisted high angular resolution images obtained with the NACO instrument at the ESO VLT. Through optimised PSF fitting we remove the light from all detected stars above a given magnitude limit. Subsequently we analyse the remaining, diffuse light density. The analysed diffuse light arises from sub-giant and main-sequence stars with KS ~ 19 - 20 with masses of 1 - 2 Msol . These stars can be old enough to be dynamically relaxed. The observed power-law profile and its slope are consistent with the existence of a relaxed stellar cusp around the Milky Ways central black hole. We find that a Nuker law provides an adequate description of the nuclear clusters intrinsic shape (assuming spherical symmetry). The 3D power-law slope near Sgr A* is gamma = 1.23 +- 0.05. At a distance of 0.01 pc from the black hole, we estimate a stellar mass density of 2.3 +- 0.3 x 10^7 Msol pc^-3 and a total enclosed stellar mass of 180 +- 20 Msol. These estimates assume a constant mass-to-light ratio and do not take stellar remnants into account. The fact that no cusp is observed for bright (Ks 16) giant stars at projected distances of roughly 0.1-0.3 pc implies that some mechanism has altered their appearance or distribution.