Ubiquitination, the conserved proteasome system, is a PTM which relates to numerous biological processes, such as protein degradation, endocytosis, and cell cycle. Numerous ubiquitination sites remain undiscovered because of the limitations of mass spectrometry-based methods. In fact, some sites that undergo ubiquitination have not been identified. Hence, these machine learning-based prediction methods suffer from no reliable database of non-ubiquitination sites. Existing prediction methods use randomly selected non-validated sites as non-ubiquitination sites to train ubiquitination site prediction models. In this work, we propose an evolutionary screening algorithm (ESA) to select effective negatives from among non-validated sites and an ESA-based prediction method, ESA-UbiSite, to identify human ubiquitination sites. The ESA selects non-validated sites least likely to be ubiquitination sites as training negatives. Experimental results show that ESA-UbiSite with effective negatives achieved 0.92 test accuracy, better than existing prediction methods.