Margaret "Maggie" O'Keefe (Annie Golden) was Cliff's love interest from Season 7 onward. Maggie first appeared in Season 7 as a rookie postal carrier who was to be trained by Cliff. Maggie asked Cliff out, and he accepted. However, Maggie was later caught taking a postal vehicle to a motel, and was fired from the post office. She then left Cliff to go to Canada, to join the Canadian post office. She made regular appearances from then on, which led to her and Cliff's on-again off-again relationship.

In the episode "Do Not Forsake Me, O' my Postman" (Season 11), Maggie reappeared and informed Cliff that she was pregnant with Cliff's child. This forced Cliff to admit that he and Maggie never went to bed together, causing the other barflies to mock him. Cliff agrees to marry Maggie but before they depart she decides to call her childs real father so he won't worry anymore. She then tells Norm that the father is upset someone else will be raising his child and that he wants to marry her and Cliff is off the hook. However, as she leaves she tells Cliff they did have sex, twice, though he was apparently inebriated and didn't remember. It's left unclear to the viewer whether or not this was true.