We study, both experimentally and theoretically, short-time modifications of the decay of excitations in a Bose-Einstein Condensate (BEC) embedded in an optical lattice. Strong enhancement of the decay is observed compared to the Golden Rule results. This enhancement of decay increases with the lattice depth. It indicates that the description of decay modifications of few-body quantum systems also holds for decay of many-body excitations of a BEC.