We present deep galaxy counts in the K (lambda 2.2 mu m) band, obtained at the W. M. Keck 10 m telescope. The data reach limiting magnitudes K similar to 24 mag, about 5 times deeper than the deepest published K-band images to date. The counts are performed in three small (similar to 1'), widely separated high-latitude fields. Extensive Monte Carlo tests were used to derive the completeness corrections and minimize photometric biases. The counts continue to rise, with no sign of a turnover, down to the limits of our data, with the logarithmic slope of d log N/dm = 0.315 +/- 0.02 between K = 20 and 24 mag. This implies a cumulative surface density of similar to 5 x 10(5) galaxies deg(-2), or similar to 2 x 10(10) over the entire sky, down to K = 24 mag. Our counts are in good agreement with, although slightly lower than, those from the Hawaii Deep Survey by Cowie and collaborators; the discrepancies may be due to the small differences in the aperture corrections. The observed field-to-field variations are as expected from the Poissonian noise and galaxy clustering as described by the angular two-point correlation function for faint galaxies. We compare our counts with some of the available theoretical predictions. The data do not require models with a high value of Omega(0), but can be well fitted by models with no (or little) evolution, and cosmologies with a low value of Omega(0). Given the uncertainties in the models, it may be premature to put useful constrains on the value of Omega(0) from the counts alone. Optical-to-IR colors are computed, using CCD data obtained previously at Palomar. We find a few red galaxies with (r - K) greater than or similar to 5 mag, or (i - K) greater than or similar to 5 mag; these may be ellipticals at z similar to 1. While the redshift distribution of galaxies in our counts is still unknown, the flux limits reached would allow us to detect unobscured L* galaxies out to substantial redshifts (z > 3?).