The environment of Sagittarius A* (Sgr A*), the central black hole of the Milky Way, is the only place in the Universe where we can currently study the interaction between a nuclear star cluster and a massive black hole and infer the properties of a nuclear cluster from observations of individual stars. This work aims to explore the star formation history of the nuclear cluster and the structure of the innermost stellar cusp around Sgr A*. We combined and analysed multi epoch high quality AO observations. For the region close to Sgr A* we apply the speckle holography technique to the AO data and obtain images that are >=50% complete down to Ks~19 within a projected radius of 5" around Sgr A*. We used $H$-band images to derive extinction maps. We provide Ks photometry for roughly 39000 stars and H-band photometry for ~11000 stars within a field of about 40"x40", centred on Sgr A*. In addition, we provide Ks photometry of ~3000 stars in a very deep central field of 10"x10", centred on Sgr A*. We find that the Ks luminosity function (KLF) is rather homogeneous within the studied field and does not show any significant changes as a function of distance from the central black hole on scales of a few 0.1pc. By fitting theoretical luminosity functions to the KLF, we derive the star formation history of the nuclear star cluster. We find that about 80% of the original star formation took place 10Gyr ago or longer, followed by a largely quiescent phase that lasted for more than 5Gyr. We clearly detect the presence of intermediate-age stars of about 3Gyr in age. This event makes up about 15% of the originally formed stellar mass of the cluster. A few percent of the stellar mass formed in the past few 100Myr. Our results appear to be inconsistent with a quasi-continuous star formation history. The mean metallicity of the stars is consistent with being slightly super solar. The stellar density increases exponentially towards Sgr A* at all magnitudes between Ks=15-19. We also show that the precise properties of the stellar cusp around Sgr A* are hard to determine because the star formation history suggests that the star counts can be significantly contaminated, at all magnitudes, by stars that are too young to be dynamically relaxed. We find that the probability of observing any young (non-millisecond) pulsar in a tight orbit around Sgr A* and beamed towards Earth is very low. We argue that typical globular clusters, such as they are observed in and around the Milky Way today, have probably not contributed to the nuclear cluster's mass in any significant way. The nuclear cluster may have formed following major merger events in the early history of the Milky Way.