A central mechanism of action control is binding between actions and the stimuli provoking them. Perceiving the same stimuli again retrieves any bound responses, facilitating their execution. Does such binding and retrieval only emerge when stimulus-response rules are known before taking action or also when agents are forced to guess and receive feedback about the success after responding? We tested the hypothesis that knowing rules before responding would boost stimulus-response binding relative to guessing situations. We also assessed whether the content of the feedback matters for binding in that agents might use feedback to build correct stimulus-response bindings even for wrong guesses. We used a sequential prime-probe design to induce stimulus-response binding for prime responses that were either rule-based or guesses and to measure retrieval of these bindings in response times and errors in the probe. Results indicate that binding and retrieval emerges for successful but not for wrong guesses. Binding effects for correct guesses were consistently small in effect size, suggesting that pre-established stimulus-response bindings from instructed rules might indeed boost binding when taking action.