Cognitive flexibility plays a key role in ensuring an individual's survival. The prefrontal cortex and striatum are both essential to cognitive flexibility but competing theories debate which structure among these two leads the role in detecting and representing new circumstances for a change, giving largely opposing predictions on neural activities in the prefrontal cortex and striatum during flexible behavior. We trained head-restrained mice to perform an action-outcome based dynamic foraging task and simultaneously recorded single-neuron activities in the medial prefrontal cortex (mPFC) and dorsomedial striatum (DMS). We report that mPFC but not DMS activity stores information about the overall reward history of all options. A large fraction of both mPFC and DMS neurons’ activity represents the difference in reward probability between two alternative options, a key decision variable that prescribes which subsequent choice to make. We find that mPFC neural activities track the change of this variable earlier and faster than those in the DMS. Finally, functional connectivity between mPFC and DMS, increases with reducing overall reward proportion. Our results support a framework in which the prefrontal cortex is the first responder to changes in environmental variables in the prefrontostrial circuitry, and the communication between the two strengthens upon the need for change in flexible behavior.