Genome-wide yeast two-hybrid (Y2H) screens were conducted to elucidate the molecular functions of open reading frames (ORFs) encoded by murine γ-herpesvirus 68 (MHV-68). A library of 84 MHV-68 genes and gene fragments was generated in a Gateway entry plasmid and transferred to Y2H vectors. All possible pair-wise interactions between viral proteins were tested in the Y2H assay, resulting in the identification of 23 intra-viral protein-protein interactions (PPIs). Seventy percent of the interactions between viral proteins were confirmed by co-immunoprecipitation experiments. To systematically investigate virus-cellular protein interactions, the MHV-68 Y2H constructs were screened against a cellular cDNA library, yielding 243 viral-cellular PPIs involving 197 distinct cellar proteins. Network analyses indicated that cellular proteins targeted by MHV-68 had more partners in the cellular PPI network and were located closer to each other than expected by chance. Taking advantage of this observation, we scored the cellular proteins based on their network distances from other MHV-68-interacting proteins and segregated them into high (Y2H-HP) and low priority/not-scored (Y2H-LP/NS) groups. Significantly more genes from Y2H-HP altered MHV-68 replication when their expression was inhibited with siRNAs (53% of genes from Y2H-HP, 21% of genes from Y2H-LP/NS, and 16% of genes randomly chosen from the human PPI network; p<0.05). Enriched Gene Ontology (GO) terms in the Y2H-HP group included regulation of apoptosis, protein kinase cascade, post-translational protein modification, transcription from RNA polymerase II promoter, and IκB kinase/NFκB cascade. Functional validation assays indicated that PCBP1, which interacted with MHV-68 ORF34, may be involved in regulating late virus gene expression in a manner consistent with the effects of its viral interacting partner. Our study integrated Y2H screening with multiple functional validation approaches to create γ-herpes viral-viral and viral-cellular protein interaction networks.