We describe the full exit boundary of random walks on homogeneous trees, in particular, on the 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, probability and was fully stated in a series of recent papers by the first author \cite{V1,V2,V3}. 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.