A class of permutations Pi is called hereditary if pi <* sigma in Pi  implies pi in Pi, where the relation <* is the natural containment of permutations. Let Pi_n be the set of all permutations of 1,2, ..., n belonging to Pi. We investigate the counting functions n -> |Pi_n| of hereditary classes. Our main result says that if |Pi_n| < 2^{n-1} for at least one n >= 1, then there is a unique k >= 1 such that F_{n,k} <= |Pi_n| <= F_{n,k}.n^c holds for all n >=1 with a constant c>0. Here F_{n,k} are the generalized Fibonacci numbers which grow like powers of the largest positive root of x^k - x^{k-1} - ... - 1. We characterize also the constant and the polynomial growth of hereditary permutation classes and give two more results on these.