The original definition of amenability given by von Neumann in the highly non-constructive terms of means was later recast by Day using approximately invariant probability measures. Moreover, as it was conjectured by Furstenberg and proved by Kaimanovich-Vershik and Rosenblatt, the amenability of a locally compact group is actually equivalent to the existence of a single probability measure on the group with the property that the sequence of its convolution powers is asymptotically invariant. In the present article we extend this characterization of amenability to measured groupoids. It implies, in particular, that the amenability of a measure class preserving group action is equivalent to the existence of a random environment on the group parameterized by the action space, and such that the tail of the random walk in almost every environment is trivial.