During DNA replication and repair, many proteins bind to and dissociate in a highly specific and ordered manner from proliferating cell nuclear antigen (PCNA). We describe a combined approach of in silico searches at the genome level and combinatorial peptide synthesis to investigate the binding properties of hundreds of short PCNA-interacting peptides (PIP-peptides) to archaeal and eukaryal PCNAs. Biological relevance of our combined approach was demonstrated by identification an inactive complex of Pyrococcus abyssi ribonuclease HII with PCNA. Furthermore we show that PIP-peptides interact with PCNA largely in a sequence independent manner. Our experimental approach also identified many so far unidentified PCNA interacting peptides in a number of human proteins.