This phrase have become a popular meme in the Internet, but it dates to at least 1970's. The earliest example I know is Monty Python's "Army Protection Racket" sketch:
Luigi: (Michael Palin) (looking round office casually) You've... you've got a nice army base here, Colonel.
Colonel: Yes.
Luigi: We wouldn't want anything to happen to it.
Colonel: What?
Dino: No, what my brother means is it would be a shame if... (he knocks something off mantel)
However, they were likely using an already stereotypical Mafia threat. So, when did such a phrase first appear?