To a Boolean inverse monoid S we associate a universal C*-algebra C-B (S) and show that it is equal to Exel's tight C*-algebra of S. We then show that any invariant mean on S (in the sense of Kudryavtseva, Lawson, Lenz and Resende) gives rise to a trace on C-B(S), and vice-versa, under a condition on S equivalent to the underlying groupoid being Hausdorff. Under certain mild conditions, the space of traces of C-B (S) is shown to be isomorphic to the space of invariant means of S. We then use many known results about traces of C*-algebras to draw conclusions about invariant means on Boolean inverse monoids; in particular we quote a result of Blackadar to show that any metrizable Choquet simplex arises as the space of invariant means for some AF inverse monoid S.