In recent work with Harman, we introduced a notion of measure on a class of finite relational structures. In this note, we consider measures on the class of permutations, i.e., finite sets with two total orders. Using a method of Nekrasov, we show that there are exactly 37 measures. Two of these measures lead to a new pre-Tannakian tensor category.