We present K-band number counts for the faint galaxies in the Calar Alto Deep Imaging Survey (CADIS). We covered 4 CADIS fields, a total area of 0.2deg^2, in the broad band filters B, R and K. We detect about 4000 galaxies in the K-band images, with a completeness limit of K=19.75mag, and derive the K-band galaxy number counts in the range of 14.25 < K < 19.75mag. This is the largest medium deep K-band survey to date in this magnitude range. The B- and R-band number counts are also derived, down to completeness limits of B=24.75mag and R=23.25mag. The K-selected galaxies in this magnitude range are of particular interest, since some medium deep near-infrared surveys have identified breaks of both the slope of the K-band number counts and the mean B-K color at K=17\sim18mag. There is, however, a significant disagreement in the K-band number counts among the existing surveys. Our large near-infrared selected galaxy sample allows us to establish the presence of a clear break in the slope at K=17.0mag from dlogN/dm = 0.64 at brighter magnitudes to dlogN/dm = 0.36 at the fainter end. We construct no-evolution and passive evolution models, and find that the passive evolution model can simultaneously fit the B-, R- and K-band number counts well. The B-K colors show a clear trend to bluer colors for K > 18mag. We also find that most of the K=18-20mag galaxies have a B-K color bluer than the prediction of a no-evolution model for an L_* Sbc galaxy, implying either significant evolution, even for massive galaxies, or the existence of an extra population of small galaxies.