Every unitary involutive solution of the quantum Yang-Baxter equation ("R-matrix") defines an extremal character and a representation of the infinite symmetric group $S_\infty$. We give a complete classification of all such Yang-Baxter characters and determine which extremal characters of $S_\infty$ are of Yang-Baxter form. Calling two involutive R-matrices equivalent if they have the same character and the same dimension, we show that equivalence classes are classified by pairs of Young diagrams, and construct an explicit normal form R-matrix for each class. Using operator-algebraic techniques (subfactors), we prove that two R-matrices are equivalent if and only if they have similar partial traces. Furthermore, we describe the algebraic structure of the equivalence classes of all involutive R-matrices, and discuss several classes of examples. These include Yang-Baxter representations of the Temperley-Lieb algebra at parameter $q=2$, which can be completely classified in terms of their rank and dimension.