We present the results of a very deep K-band survey with a 5 sigma total galaxy magnitude limit of K = 21.9 in the deepest field. A 5 sigma K-band-selected sample of 123 galaxies is presented, together with their optical colors. Only three galaxies in this sample are not detected at the 1 sigma level in Kron-Cousins I band. At K less than or = 20 the reddest (I-K) color is 5.1 +/- 0.4, and 15 of the 123 objects in the deep field sample have (I-K) greater than 4. In the blue, the galaxies show a rapid blueward trend at magnitudes beyond K = 19, dropping from a median (B-K) = 6 at K = 18 to a median (B-K) of only 4.2 at K = 21.5. The surface density of (I-K) greater than 4 objects is interpreted to imply either that there is a significant evolution toward later types in the colors of the normal galaxy population beyond z = 11 or that galaxies have faded by that redshift.