Immediately after bacteriophage infection, phage early proteins establish optimal conditions for phage infection, often through a direct interaction with host-cell proteins. We implemented a yeast two-hybrid approach for Pseudomonas aeruginosa phages as a first step in the analysis of these - often uncharacterized - proteins. A 24-fold redundant prey library of P. aeruginosa PAO1 (7.32x10(6) independent clones), was screened against early proteins (gp1 to 9) of phiKMV, a P. aeruginosa-infecting member of the Podoviridae; interactions were verified using an independent in vitro assay. None resembles previously known bacteriophage-host interactions, as the three identified target malate synthase G, a regulator of a secretion system and a regulator of nitrogen assimilation. Although at least two-bacteriophage infections are non-essential to phiKMV infection, their disruption has an influence on infection efficiency. This methodology allows systematic analysis of phage proteins and is applicable as an interaction analysis tool for P. aeruginosa.