In this paper we present the results of the first systematic search for counterparts to nearby ultraluminous X-ray sources (ULXs) in the near-infrared (NIR). We observed 62 ULXs in 37 galaxies within 10 Mpc and discovered 17 candidate NIR counterparts. The detection of 17 out of 62 ULX candidates points to intrinsic differences between systems that show and those that do not show infrared emission. For six counterparts we conclude from the absolute magnitudes and - - in some cases - additional information such as morphology and previously reported photometric or spectroscopic observations, that they are likely background active galactic nuclei or ULXs residing in star clusters. Eleven counterparts have absolute magnitudes consistent with them being single red supergiant stars. Alternatively, these systems may have larger accretion discs that emit more NIR light than the systems that we do not detect. Other scenarios such as emission from a surrounding nebula or from a compact radio jet are also possible, although for Holmberg II X-1 the NIR luminosity far exceeds the expected jet contribution. The eleven possible red supergiant counterparts are excellent candidates for spectroscopic follow-up observations. This may enable us to measure the mass function in these systems if they are indeed red supergiant donor stars where we can observe absorption lines.

16 pages, 3 figures, 5 tables, accepted for publication in MNRAS