It is challenging to decipher molecular mechanisms in biological systems from system-level input-output data, especially for complex processes that involve interactions among multiple components. We addressed this general problem for the bacterial histidine kinase CheA, the activity of which is regulated in chemotaxis signaling complexes by bacterial chemoreceptors. We developed a general network model to describe the dynamics of the system, treating the receptor complex with coupling protein CheW and the P3P4P5 domains of kinase CheA as a regulated enzyme with two substrates, ATP and P1, the phosphoryl-accepting domain of CheA. Our simple network model allowed us to search hypothesis space systematically. For different and progressively more complex regulation schemes, we fit our models to a large set of input-output data with the aim of identifying the simplest possible regulation mechanisms consistent with the data. Our modeling and analysis revealed novel dual regulation mechanisms in which receptor activity regulated ATP binding plus one other process, either P1 binding or phosphoryl transfer between P1 and ATP. Strikingly, in our models receptor control affected the kinetic rate constants of substrate association and dissociation equally and thus did not alter the respective equilibrium constants. We suggest experiments that could distinguish between the two dual-regulation mechanisms. This systems-biology approach of combining modeling and a large input-output dataset should be applicable for studying other complex biological processes.