We describe the full exit boundary of random walks on homogeneous trees, in particular, on free groups. This model exhibits a phase transition; namely, the family of Markov measures under study loses ergodicity as a parameter of the random walk changes. The problem under consideration is a special case of the problem of describing the invariant (central) measures on branching graphs, which covers a number of problems in combinatorics, representation theory, and probability and was fully stated in a series of recent papers by the first author [1]–[3]. On the other hand, in the context of the theory of Markov processes, close problems were discussed as early as 1960s by E. B. Dynkin.