Humans have the unique ability to efficiently execute instructions that were never practiced beforehand. In this Rapid Instructed-Task-Learning, not-yet-executed novel rules are presumably held in procedural working-memory (WM), which is assumed to hold stimulus-to-response bindings. In this study, we employed a computerized-cognitive training protocol targeting procedural WM to test this assumption and to examine whether the ability to rapidly learn novel rules can itself be learned. 175 participants were randomly assigned to one of three groups: procedural WM training (involving task-switching and N-back elements, all with novel rules; Shahar and Meiran in PLoS One 10(3):e0119992, 2015), active-control training (adaptive visual-search task), and no-contact control. We examined participants' rapid instructed-task-learning abilities before and after training, by administrating 55 novel choice tasks, and measuring their performance in the first two trials (where participants had no practice). While all participants showed shorter reaction-times in post vs. pretest, only participants in the procedural WM training group did not demonstrate an increased error rate at posttest. Evidence accumulation modelling suggested that this result stems from a reduction in decision threshold (the amount of evidence that needs to be gathered to reach a decision), which was more pronounced in the control groups; possibly accompanied by an increased drift-rate (the rate of evidence accumulation) only for the training group. Implication are discussed.