(abridged) We provide Ks photometry for roughly 39,000 stars and H-band photometry for about 11,000 stars within a field of about 40"x40", centred on Sgr A*. In addition, we provide Ks photometry of about 3,000 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.1 pc. 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 10 Gyr ago or longer, followed by a largely quiescent phase that lasted for more than 5 Gyr. We clearly detect the presence of intermediate-age stars of about 3 Gyr 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 100 Myr. Our results appear to be inconsistent with a quasi-continuous star formation history. The stellar density increases exponentially towards Sgr A* at all magnitudes between Ks=15 to 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.