ALG-2 (also named PDCD6) is a 22-kDa Ca(2+)-binding protein that belongs to the penta-EF-hand family including calpain small subunit and interacts with various proteins such as ALIX and Sec31A at their specific sites containing an ALG-2-binding motif (ABM) present in their respective Pro-rich region (PRR). In this study, to search for novel ALG-2-interacting proteins, we first performed in silico screening of ABM-containing PRRs in a human protein database. After selecting 17 sequences, we expressed the PRR or full-length proteins fused with green fluorescent protein (GFP) in HEK293T cells and analysed their abilities to bind to ALG-2 by Far-Western blotting using biotinylated ALG-2 as a probe. As a result, we found 10 positive new ALG-2-binding candidates with different degrees of binding ability. For further investigation, we selected PATL1 (alternatively designated Pat1b), a component of the P-body, which is a cytoplasmic non-membranous granule composed of translation-inactive mRNAs and proteins involved in mRNA decay. Interactions between endogenous PATL1 and ALG-2 proteins were demonstrated by a co-immunoprecipitation assay using their specific antibodies. Furthermore, in immunofluorescence microscopic analyses, PATL1 as well as DCP1A, a well-known P-body marker, co-localized with a subset of ALG-2. This is the first report showing interaction of ALG-2 with a P-body component.