Gap genes are among the first transcriptional targets of maternal morphogen gradients in the early Drosophila embryo. However, it remains unclear whether these gradients are indeed sufficient to establish the boundaries of localized gap gene expression patterns. In this study, we address this question using gap gene circuits, which are data-driven mathematical tools for extracting regulatory information from quantitative wild-type gene expression data. We present new, quantitative data on the mRNA expression patterns for the gap genes Krüppel (Kr), knirps (kni) and giant (gt) during the early blastoderm stage of Drosophila development. This data set shows significant differences in timing of gap gene expression compared to previous observations, and reveals that early gap gene expression is highly variable in both space and time. Gene circuit models fit to this data set were used for a detailed regulatory analysis of early gap gene expression. Our analysis shows that the proper balance of maternal repression and activation is essential for the correct positioning of gap domains, and that such balance can only be achieved for early expression of kni. In contrast, our results suggest that early expression of gt requires local neutralization of repressive input in the anterior region of the embryo, and that known maternal gradients are completely insufficient to position the boundaries of the early central Kr domain, or in fact any Kr-like domain in the central region of the blastoderm embryo. Based on this, we propose that unknown additional regulators must be involved in early gap gene regulation.