Memory formation and storage rely on multiple interconnected brain areas, the contribution of which varies during memory consolidation. The medial prefrontal cortex, in particular the prelimbic cortex (PL), was traditionally found to be involved in remote memory storage, but recent evidence points toward its implication in early consolidation as well. Nevertheless, the inputs to the PL governing these dynamics remain unknown. Here, we first performed a brain-wide, rabies-based retrograde tracing screen of PL engram cells activated during contextual fear memory formation in male mice to identify relevant PL input regions. Next, we assessed the specific activity pattern of these inputs across different phases of memory consolidation, from fear memory encoding to recent and remote memory recall. Using projection-specific chemogenetic inhibition, we then tested their functional role in memory consolidation, which revealed a hitherto unknown contribution of claustrum to PL inputs at encoding, and of insular cortex to PL inputs at recent memory recall. Both of these inputs further impacted how PL engram cells were reactivated at memory recall, testifying to their relevance for establishing a memory trace in the PL. Collectively, these data identify a spatiotemporal shift in PL inputs important for early memory consolidation, and thereby help to refine the working model of memory formation.