An n-element permutation is called k-balanced if every k-element permutation occurs in it equally often, through order-isomorphism. We explicitly construct k-balanced permutations for k ≤ 3, and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for k ≥ 4, no such permutations exist, and in fact every n-element permutation is at least Ω(n^(k−1)) far from being k-balanced. This lower bound is matched for k = 4, by a construction based on the Erdős-Szekeres permutation. Joint work with Gal Beniamini and Nati Linial.