The paper considers a fuzzification of the notion of quantaloid of K. I. Rosenthal, which replaces enrichment in the category of ⋁-semilattices with that in the category of modules over a given unital commutative quantale. The resulting structures are called quantale algebroids. We show that their constitute a monadic category and prove a representation theorem for them using the notion of nucleus adjusted for our needs. We also characterize the lattice of nuclei on a free quantale algebroid. At the end of the paper, we prove that the category of quantale algebroids has a monoidal structure given by tensor product.