He was imprisoned in the Gnome Zone by evil gnomes for a long while, before Malphoid found him and broke him out of his cage. The two escaped from the Gnome Zone, and became partners. Lester helped Malphoid deliver the mail for the rest of the day, although they ran out of time and Malphoid was fired. (Malphoid Series: "Malphoid the Mailbox Bot")
Lester, however, was not, and continued working for Newman. Malphoid got a new job with the U.P.S., making him Lester’s opponent. Lester was extremely loyal to Newman, and didn't care about his partner Malphoid. (Malphoid Series: "Malphoid: Fired!")
When Malphoid was on a quest to assemble an advanced, godlike machine, Lester stood in his way at every turn. However, Malphoid still managed to assemble the machine and turned it on Newman.
Once Newman was defeated, Lester saved his life. Shortly thereafter, he approached Malphoid and gained his trust. This way, he helped Malphoid bury the machine in a discreet location. He then betrayed Malphoid and gave the machine's location to Newman, who was now becoming The Collector.
When The Collector unearthed the machine, Lester continued to serve him and help him. They were able to defeat Malphoid using the machine, and imprison him. (Space-Balls Series: "Tutorial Bot's Past")