Gid4, a subunit of the ubiquitin ligase GID, is the recognition component of the Pro/N-degron pathway. Gid4 targets proteins in particular through their N-terminal (Nt) proline (Pro) residue. In Saccharomyces cerevisiae and other Saccharomyces yeasts, the gluconeogenic enzymes Fbp1, Icl1, and Mdh2 bear Nt-Pro and are conditionally destroyed by the Pro/N-degron pathway. However, in mammals and in many non-Saccharomyces yeasts, for example, in Kluyveromyces lactis, these enzymes lack Nt-Pro. We used K. lactis to explore evolution of the Pro/N-degron pathway. One question to be addressed was whether the presence of non-Pro Nt residues in K. lactis Fbp1, Icl1, and Mdh2 was accompanied, on evolutionary time scales (S. cerevisiae and K. lactis diverged ∼150 million years ago), by a changed specificity of the Gid4 N-recognin. We used yeast-based two-hybrid binding assays and protein-degradation assays to show that the non-Pro (Ala) Nt residue of K. lactis Fbp1 makes this enzyme long-lived in K. lactis. We also found that the replacement, through mutagenesis, of Nt-Ala and the next three residues of K. lactis Fbp1 with the four-residue Nt-PTLV sequence of S. cerevisiae Fbp1 sufficed to make the resulting "hybrid" Fbp1 a short-lived substrate of Gid4 in K. lactis. We consider a blend of quasi-neutral genetic drift and natural selection that can account for these and related results. To the best of our knowledge, this work is the first study of the ubiquitin system in K. lactis, including development of the first protein-degradation assay (based on the antibiotic blasticidin) suitable for use with this organism.