The Stooges operate a Middle Eastern restaurant called Cafe Casbah Bah, where they become entangled in a string of mishaps while serving patrons Hassan ben Sober and Ginna Rumma.

A culinary incident ensues when spaghetti inadvertently splatters onto the patrons' faces, prompting the Stooges to offer a replacement meal of rabbit and hot dogs.

A scene closely resembling the lobby card is in the finished film (with Hassan ben Sober in Curly's stead); ultimately Larry assumed the role as the chef.

Malice in the Palace is one of four Columbia Stooge shorts that fell into the public domain after their copyright expired in the 1960s, the other three being Sing a Song of Six Pants, Brideless Groom (both 1947), and Disorder in the Court (1936).

The routine where Hassan ben Sober and Ginna Rumma believe they are eating real rabbit and dog also appeared in the Abbott and Costello film The Naughty Nineties four years earlier.