The conditional Entropy Power Inequality is a fundamental inequality in information theory, stating that the conditional entropy of the sum of two conditionally independent vector-valued random variables each with an assigned conditional entropy is minimum when the random variables are Gaussian. We prove two new quantum generalizations of the conditional Entropy Power Inequality. In the first one, the vector-valued random variables are still classical but the conditioning system is quantum. In the second one, the conditioning system is quantum and the vector-valued random variables are replaced by quantum states of a Gaussian quantum system. The proof is based on the heat semigroup and on a generalization of the Stam inequality in the presence of quantum conditioning. The Entropy Power Inequalities with quantum conditioning will be key tools of quantum information. Among their many possible applications there are the proof of a new uncertainty relation for the conditional Wehrl entropy and converse theorems in distributed source coding protocols with the assistance of quantum entanglement.