Cleveland's Deli was a deli owned by Cleveland Brown.
In "There's Something About Paulie", it is revealed that Peter Griffin's usual order is everything on the menu.
In "Hell Comes to Quahog", the deli is run out of business by Superstore USA, but reopens after the meltdown of the latter. It is revealed in this episode that it is located next to Goldman's Pharmacy.
In "One if by Clam, Two if by Sea", the deli is severely damaged by the hurricane, but Brown is seen rebuilding it.
It's interior was seen in "There's Something About Paulie" and in "Model Misbehavior".
In "Not All Dogs Go To Heaven", Stewie Griffin steals the deli delivery truck to drive the cast of Star Trek: The Next Generation to McDonald's.
When Cleveland leaves Quahog in the pilot episode of The Cleveland Show, he announces his intent to sell the deli.
After trying his hand at a therapist until he angers his friends in "Dr. C & The Women", Cleveland returns to his former deli, which has been abandoned since he left Quahog, to hide out.