Constantine is Fry's ex-girlfriend Michelle's new boyfriend, who she just met on New Year's, 1999. Two hours later, while they were making out, Bender mistakes him for Fry for a moment, but Michelle tells him about his blunder, and after checking his ass for a time tattoo of his own face, he continues his search.
Years later, Constantine attended law school, while Michelle became a dog walker. But at graduation, Cosntantine left Michelle for someone else, so she froze herself and coincidentally met Fry in the future.
In The Cryonic Women, it was revealed that Constantine's name is really Charles.