Phosphoprotein phosphatase (PPP) enzymes are ubiquitous proteins involved in cellular signaling pathways and other functions. Here we have traced the origin of the PPP sequences of Eukaryotes and their radiation. Using a bacterial PPP Hidden Markov Model (HMM) we uncovered "BacterialPPP-Like" sequences in Archaea. A HMM derived from eukaryotic PPP enzymes revealed additional, unique sequences in Archaea and Bacteria that were more like the eukaryotic PPP enzymes then the bacterial PPPs. These sequences formed the basis of phylogenetic tree inference and sequence structural analysis allowing the history of these sequence types to be elucidated. Our phylogenetic tree data strongly suggest that eukaryotic PPPs ultimately arose from ancestors in the Asgard archaea. We have clarified the radiation of PPPs within Eukaryotes, substantially expanding the range of known organisms with PPP subtypes (Bsu1, PP7, PPEF/RdgC) previously thought to have a more restricted distribution. Surprisingly, sequences from the Methanosarcinaceae (Euryarchaeota) form a strongly supported sister group to eukaryotic PPPs in our phylogenetic analysis. This strongly suggests an intimate association between an Asgard ancestor and that of the Methanosarcinaceae. This is highly reminiscent of the syntrophic association recently demonstrated between the cultured Lokiarchaeal species Prometheoarchaeum and a methanogenic bacterial species.