The present functional magnetic resonance imaging study investigated the instruction-based learning of novel arbitrary stimulus-response mappings in order to understand the brain mechanisms that enable successful behavioral rule implementation in the absence of trial-and-error learning. We developed a novel task design that allowed the examination of rapidly evolving brain activation dynamics starting from an explicit instruction phase and further across a short behavioral practice phase. As a first key result, the study revealed that different sets of brain regions displayed either decreasing or increasing activation profiles already across the first few practice trials, suggesting an impressively rapid redistribution of labor throughout the brain. Furthermore, behavioral performance improvement across practice was tightly coupled with brain activation during the practice phase (caudate nucleus), the instruction phase (lateral midprefrontal cortex), or both (lateral premotor cortex bordering prefrontal cortex). Together, the present results provide first important insights into the brain systems involved in the rapid transfer of control from initially abstract rule representations induced by explicit instructions toward pragmatic representations enabling the fluent behavioral implementation.