The series was created as a mystery, police and crime drama spin-off of the PBS show Masterpiece Theatre.

A PBS veteran, animator Lamb had also created programming for series like Sesame Street, The Electric Company, and The Great American Dream Machine.

Because executive producer Joan Wilson was looking for a 75-second sequence, Gorey was eventually asked to hand over the drawings and allow animators to use his work as inspiration.

Gorey, known for his eccentric and stubborn nature, recounted: When we first started talking about it, I gave them a scenario for the credits, but they said, 'Thank you, very much, dear, but this will take half an hour.'

In 1979, Mobil Oil head of corporate affairs Herb Schmertz offered the idea of an all-British crime series show to WGBH manager Henry Becton.

Mobil Oil was already the underwriter for Masterpiece Theater and had seen success with high-profile British series, including The Six Wives of Henry VIII and Elizabeth R. By 1979, WGBH was bringing in a diverse array of British programming, to the point that Mobil saw an advantage to creating a unique time slot for the crime/police drama genre.

Then Masterpiece Theater host Alistair Cooke initially bemoaned the loss of the crime genre: I tell you one thing that makes life a little more difficult in choosing was since the arrival of Mystery.

Agatha Christie sleuths Hercule Poirot (David Suchet) and Miss Marple (at various times Joan Hickson, Geraldine McEwan, and Julia McKenzie) have also been featured.

We’re about to set out on a series of entertaining mysteries—15 weeks of suspenseful, sophisticated, crafty conundrums that are darkly diabolical or amusing adventures with introductions that suddenly seem alarmingly alliterative.”[2]: 10  Shalit left the show in 1981.

Rigg had previously won a BAFTA Award for her work on Masterpiece Theater's 1985 Bleak House adaptation.

PBS had avoided adding 30-second advertisements before programming blocks, despite underwriters’ requests for more robust representation on the channel.

As a result of Mobil's initial break from Mystery!, Eaton and her staff began looking for newer, more “relevant” stories to tell in both shows.

Prime Suspect had gained a strong following in the US as well as England, so PBS re-ran Series 4 on Masterpiece Theater during the 1995-1996 season.

continued as a summer series from 2002 to 2004 with shows like The Inspector Lynley Mysteries, Hetty Wainthropp Investigates and Foyle's War.

Rebecca Eaton reflected on the 2008 changes in an interview with Diane Rehm, citing Mobil’s departure, a competitive media landscape, and trouble branding Masterpiece Theater and Mystery!

But we got a grant from the Corporation for Public Broadcasting and PBS which we were pretty much allowed to do anything with...we spent it on doing some research into how people perceived Masterpiece.

It was just sort of getting past the rather forbidding title of Masterpiece Theater and the confusing anthology nature.”[11] The American Mystery!

They were based on Tony Hillerman's Navajo Tribal Police stories featuring Joe Leaphorn, played by Wes Studi, and Jim Chee, portrayed by Adam Beach: