For a graph and a positive integer , let denote the multigraph obtained by replacing each edge of with parallel edges. Let be a multigraph with edge multiplicity and with as its underlying simple graph. We find necessary and sufficient conditions for the existence of a -decomposition of for all positive integers and .