In this paper we study the C*-envelope of the (non-self-adjoint) tensor algebra associated via subproduct systems to a finite irreducible stochastic matrix $P$. Firstly, we identify the boundary representations of the tensor algebra inside the Toeplitz algebra, also known as its non-commutative Choquet boundary. As an application, we provide examples of C*-envelopes that are not *-isomorphic to either the Toeplitz algebra or the Cuntz-Pimsner algebra. This characterization required a new proof for the fact that the Cuntz-Pimsner algebra associated to $P$ is isomorphic to $C(mathbb{T}, M_d(mathbb{C}))$, filling a gap in a previous paper. We then proceed to classify the C*-envelopes of tensor algebras of stochastic matrices up to *-isomorphism and stable isomorphism, in terms of the underlying matrices. This is accomplished by determining the K-theory of these C*-algebras and by combining this information with results due to Paschke and Salinas in extension theory. This classification is applied to provide a clearer picture of the various C*-envelopes that can land between the Toeplitz and the Cuntz-Pimsner algebras.