We present a model of adaptive regulatory networks consisting of a simple biologically motivated rewiring procedure coupled to an elementary stability criterion. The resulting networks exhibit a characteristic stationary heavy-tailed degree distribution, show complex structural microdynamics, and self-organize to a dynamically critical state. We show analytically that the observed criticality results from the formation and breaking of transient feedback loops during the adaptive process.