Given the complexity of developmental networks, it is often difficult to predict the effect of genetic perturbations, even within coding genes. Regulatory factors generally have pleiotropic effects, exhibit partially redundant roles, and regulate highly interconnected pathways with ample cross-talk. Here, we delineate a logical model encompassing 48 components and 82 regulatory interactions involved in mesoderm specification during Drosophila development, thereby providing a formal integration of all available genetic information from the literature. The four main tissues derived from mesoderm correspond to alternative stable states. We demonstrate that the model can predict known mutant phenotypes and use it to systematically predict the effects of over 300 new, often non-intuitive, loss- and gain-of-function mutations, and combinations thereof. We further validated several novel predictions experimentally, thereby demonstrating the robustness of model. Logical modelling can thus contribute to formally explain and predict regulatory outcomes underlying cell fate decisions.