Let (S, H) be a polarized K3 surface. We define Brill-Noether filtration on moduli spaces of vector bundles on S. Assume that (c 1(E), H) > 0 for a sheaf E in the moduli space. We give a formula for the expected dimension of the Brill-Noether subschemes. Following the classical theory for curves, we give a notion of Brill-Noether generic K3 surfaces. Studying correspondences between moduli spaces of coherent sheaves of different ranks on S, we prove our main theorem: polarized K3 surface which is generic in the sense of moduli is also generic in the sense of Brill-Noether theory (here H is the positive generator of the Picard group of S). The harder part of the proof is proving the non-emptiness of the Brill-Noether loci. In the case of algebraic curves such a theorem, proved by Griffiths and Harris and, independently, by Lazarsfeld, is sometimes called the strong theorem of the Brill-Noether theory. We finish by considering a number of projective examples. In particular, we construct explicitly Brill-Noether special K3 surfaces of genus 5 and 6 and show the relation with the theory of Brill-Noether special curves.