Maintaining a continuous, stable perception of the visual world relies on the ability to integrate information from previous fixations with the current one. An essential component of this integration is trans-saccadic memory (TSM), memory for information across saccades. TSM capacity may play a limiting role in tasks requiring efficient trans-saccadic integration, such as multiple-fixation visual search tasks. We estimated TSM capacity and investigated its relationship to visual short-term memory (VSTM) using two visual search tasks, one in which participants maintained fixation while saccades were simulated and another where participants made a sequence of actual saccades. We derived a memory-limited ideal observer model to estimate lower-bounds on memory capacities from human search performance. Analysis of the single-fixation search task resulted in capacity estimates (4–8 bits) consistent with those reported for traditional VSTM tasks. However, analysis of the multiple-fixation search task resulted in capacity estimates (15–32 bits) significantly larger than those measured for VSTM. Our results suggest that TSM plays an important role in visual search tasks, that the effective capacity of TSM is greater than or equal to that of VSTM, and that the TSM capacity of human observers significantly limits performance in multiple-fixation visual search tasks.