The study examined human performance and related neural mechanisms in a pop-out search with different probabilities of target location and the relation between the target location and feature. In a search array, we introduced the binding relation between two target features and two kinds of location probability. Moreover, in the second half of the experiment, such a probability pattern for location/feature binding was reversed. Behavioral results revealed successful statistical learning of probability for both absolute target location and target’s location-feature binding indicated by faster RTs in the high-probability conditions for both location and location-feature binding. Moreover, the learning benefit for the probability of location-feature binding acquired during 1st (training) phase was still expressed in the 2nd (reversal) phase despite the actual binding probability was reversed. ERP results suggested that both the attentional selection and response selection process were affected by such learning revealed in the difference in N2pc and LRP amplitudes between the two conditions with different binding probability in the reversal phase. An expectation to the high probability for location-feature binding was also suggested from time-frequency analysis and Multi-Variate Pattern Classification (MVPC) indicated by larger alpha ERD magnitude and lower decoding accuracy, respectively, when the target appeared at the high-binding location in the training phase instead of the reversal phase. Overall, we have demonstrated behavioral evidence and 4 EEG markers for the associative learning of the probability of relation between location and feature of target in a pop-out search.