The authors report on the magnetodielectric (MD) effect of Z-type hexaferrite Sr3Co2Fe24O41 at various temperatures and frequencies. A fairly large negative MD effect was observed with a peak near room temperature and a maximum at low frequencies. Analysis suggests that the MD effect shows a quadratic dependence on magnetization. The results were discussed by considering the magnetic field induced change of transverse conical spin structure and spin-phonon coupling. This work is helpful for understanding the MD effect in materials with complicated spin structures.