In this paper, we address the problem of finding sequence motifs in substrate proteins specific to E3 ubiquitin ligases (E3s). We formulated a posterior probability distribution of sites by designing a likelihood function based on amino acid indexing and a prior distribution based on the disorderness of protein sequences. These designs are derived from known characteristics of E3 binding sites in substrate proteins. Then, we devise a collapsed Gibbs sampling algorithm for the posterior probability distribution called DegSampler. We performed computational experiments using 36 sets of substrate proteins specific to E3s and compared the performance of DegSampler with those of popular motif finders, MEME and GLAM2. The results showed that DegSampler was superior to the others in finding E3 binding motifs. Thus, DegSampler is a promising tool for finding E3 motifs in substrate proteins.