Visual search is typically guided by goals that are set within working memory. By varying the stimulus onset asynchrony (SOA) between a visual stimulus describing the target and the search display containing that target, previous studies have estimated how long it takes to implement such an attentional set. Here we investigate how long it takes to turn a visual memory representation (rather than a percept of the stimulus) into an attentional set. We used a memory-based postcueing procedure in which observers first encoded two colors into memory. A subsequent spatial cue indicated which of the two defined the relevant target color, followed by the search task. Experiment 1, which employed RT-based measures with unlimited viewing time, showed search slopes for relevant and irrelevant sets that suggested near instant guidance. However, Experiment 2 demonstrated that RT measures can suffer from severe underestimation. With temporally limited (and masked) viewing, accuracy scores showed that maximal search guidance was reached at about 400 ms. The results suggest that a visual memory can be turned into an attentional set within less than half a second. The implications for previous findings are discussed.