After failing to catch anything, a bored Bender fashions a large fish hook and attaches it to the ship's unbreakable diamond filament tether.
They set off following Zoidberg's underwater sense of smell to track him, and find the legendary lost city of Atlanta.
A documentary (narrated by Donovan) explains that Atlanta moved offshore in an effort to boost tourism but eventually sank to the bottom of the ocean under the weight of its own overdevelopment, and everyone who chose to stay in the city evolved into merpeople.
Fry settles in to enjoy his life with Umbriel, but abandons her out of disgust after she explains how sexual intercourse between merpeople works.
Club gave the episode a B, stating "The problem with Deep South is that the main plot, with Fry and Umbriel falling in love, only really exists for the punchline.