The non-abelian Hecke algebra $\mathcal{H}_{n,k}= \mathbb{C} [(S_k \wr S_n) \setminus S_{kn} / (S_k \wr S_n) ]$ can be endowed with a filtration using the orbit structures of the elements $x \in S_{kn}$ relative to the action of $S_{kn}$ on the set of $k$-partitions of $\{ 1, \cdots, kn\}$. We prove that the structure constants of the associated filtered algebra $\mathcal{F}_{n,k}$ is independent of $n$. This stability property leads to a universal algebra $\mathcal{F}$ which governs the algebras $\mathcal{F}_{n,k}$. We also prove that the structure constants of the algebras $\mathcal{H}_{n,k}$ is a polynomial in $n$.