In this article, we answer the research question “What factors affect the structural complexity of network administrative organizations (NAOs)?” The question warrants further research because of the lack of empirical studies on the topic. We design a quantitative study of the structure of all 37 European regulatory networks. Using Bayesian statistics, we analyze the new data set and test hypotheses, derived from the literature, about the factors affecting the structural complexity of NAOs. We find that networks with rule-setting tasks are strongly related to less complex NAOs, whereas networks with member-sanctioning and rule-enforcing tasks are strongly related to more complex NAOs. Theoretically, network-level tasks appear to affect NAO complexity, particularly given the implied uncertainty of those tasks, as well as the network-level operational requirements related to them.