An individual's performance on cognitive and perceptual tasks varies considerably across time and circumstances. We investigated neural mechanisms underlying such performance variability using regression-based analyses to examine trial-by-trial relationships between response times (RTs) and different facets of electrical brain activity. Thirteen participants trained five days on a color-popout visual-search task, with EEG recorded on days one and five. The task was to find a color-popout target ellipse in a briefly presented array of ellipses and discriminate its orientation. Later within a session, better preparatory attention (reflected by less prestimulus Alpha-band oscillatory activity) and better poststimulus early visual responses (reflected by larger sensory N1 waves) correlated with faster RTs. However, N1 amplitudes decreased by half throughout each session, suggesting adoption of a more efficient search strategy within a session. Additionally, fast RTs were preceded by earlier and larger lateralized N2pc waves, reflecting faster and stronger attentional orienting to the targets. Finally, SPCN waves associated with target-orientation discrimination were smaller for fast RTs in the first but not the fifth session, suggesting optimization with practice. Collectively, these results delineate variations in visual search processes that change over an experimental session, while also pointing to cortical mechanisms underlying performance in visual search.