Songfacts®:

• This song is about a young couple who have their first sexual encounter. It a rather realistic portrayal, as the guy admits he has no idea what he's doing, but has to pretend that he's an experienced lover so she'll think he's the right man for the job.
  
  When he's done, he's mystified (thus the title), as it clearly didn't meet his expectations ("I can't do it anymore and I'm not satisfied").
• Songwriting came easily to Costello; so easily that he could whip up a catchy pop song with minimal effort. That's what he did here - he later described the song as "a few ideas thrown together with a hook."
  
  His quirky tune written for his own amusement found an audience, however, and Costello ended up playing it throughout his career. It was an early lesson for him, as he had to learn to appreciate songs his fans loved even if he thought very little of them.
• "Mystery Dance" was included on Costello's first album, which was produced by Nick Lowe. Elvis didn't have his own band together at this point, but musicians from the American band Clover were brought in to record the tracks in London.
  
  On this track, Lowe played bass and piano while Clover members John McFee and Mickey Shine handled guitar and drums, respectively.
• In 2014, Showtime released a documentary called Elvis Costello: Mystery Dance that chronicles his career.