We introduce the notion of the modular class of a Lie algebroid equipped with a Nambu structure. In particular, we recover the modular class of a Nambu-Poisson manifold $M$ with its Nambu tensor $\Lambda$ as the modular class of the tangent Lie algebroid $TM$ with Nambu structure $\Lambda$. We show that many known properties of the modular class of a Nambu-Poisson manifold and that of a Lie algebroid extend to the setting of a Lie algebroid with Nambu structure. Finally, we prove that for a large class of Nambu-Poisson manifolds considered as tangent Lie algebroids with Nambu structures, the associated modular classes are closely related to Evens-Lu-Weinstein modular classes of Lie algebroids.