In workplace settings, skilled participants cooperate on the basis of shared routines in smooth and often implicit ways. Our study shows how interactional histories provide the basis for routine coordination. We draw on theater rehearsals as a perspicuous setting for tracking interactional histories. In theater rehearsals, the process of building performing routines is in focus. Our study builds on collections of consecutive performances of the same instructional task coming from a corpus of video-recordings of 30 h of theater rehearsals of (...) professional actors in German. Over time, instructions and their implementations are routinely coordinated by virtue of accumulated shared interactional experience: Instructions become shorter, the timing of responses becomes increasingly compacted and long negotiations are reduced to a two-part sequence of instruction and implementation. Overall, a routine of how to perform the scene emerges. Over interactional histories, patterns of projection of next actions emanating from instructions become reliable and can be used by respondents as sources for anticipating and performing relevant next actions. The study contributes to our understanding of how shared knowledge and routines accumulate over shared interactional experiences in publicly performed and reciprocally perceived ways and how this impinges on the efficiency of joint action. (shrink)