Earlier work has presented algorithms to factor and compute GCDs of symbolic Laurent polynomials, that is multivariate polynomials whose exponents are themselves integer-valued polynomials. This article extends the notion of univariate polynomial decomposition to symbolic polynomials and presents an algorithm to compute these decompositions. For example, the symbolic polynomial f(X) = 2Xn 2 +n - 4Xn 2 + 2Xn 2-n + 1 can be de-composed as f = g o h where g(X) = 2X2 + 1 and h(X) = Xn 2 /2+n/2 - Xn 2 /2-n/2.