In this paper, we study the problem of efficiently computing correlated itemsets satisfying given constraints. We call them valid correlated itemsets. It turns out constraints can have subtle interactions with correlated itemsets, depending on their underlying properties. We show that in general the set of minimal valid correlated itemsets does not coincide with that of minimal correlated itemsets that are valid, and characterize classes of constraints for which these sets coincide. We delineate the meaning of these two spaces and give algorithms for computing them. We also give an analytical evaluation of their performance and validate our analysis with a detailed experimental evaluation.