The operator product expansion of massless celestial primary operators of arbitrary spin is investigated. Poincaré symmetry is found to imply a set of recursion relations on the operator product expansion coefficients of the leading singular terms at tree-level in a holomorphic limit. The symmetry constraints are solved by an Euler beta function with arguments that depend simply on the right-moving conformal weights of the operators in the product. These symmetry-derived coefficients are shown not only to match precisely those arising from momentum-space tree-level collinear limits, but also to obey an infinite number of additional symmetry transformations that respect the algebra of w(1+infinity). In tree-level minimally-coupled gravitational theories, celestial currents are constructed from light transforms of conformally soft gravitons and found to generate the action of w(1+infinity) on arbitrary massless celestial primaries. Results include operator product expansion coefficients for fermions as well as those arising from higher-derivative non-minimal couplings of gluons and gravitons.