This was first said by the famous French poet Baudelaire in an unusual short story about meeting the Devil and having a grand old time.
Elle ne se plaignit en aucune façon de la mauvaise réputation dont elle jouit dans toutes les parties du monde, m'assura qu'elle était, elle-même, la personne la plus intéressée à la destruction de la superstition, et m'avoua qu'elle n'avait eu peur, relativement à son propre pouvoir, qu'une seule fois, c'était le jour où elle avait entendu un prédicateur, plus subtil que ses confrères, s'écrier en chaire:
«Mes chers frères, n'oubliez jamais, quand vous entendrez vanter le progrès des lumières, que la plus belle des ruses du diable est de vous persuader qu'il n'existe pas!»
He did not complain in any way about the bad reputation he enjoyed all over the world, assured me that he himself was the person the most interested in the destruction of superstition, and admitted to me that he had only been afraid for his own power one time, and that was the day when he had heard a preacher, more subtle than his colleagues, shout out from the pulpit:
"My dear brothers, never forget, when you hear the progress of enlightenment vaunted, that the devil's best trick is to persuade you that he doesn't exist!"
"Le Joueur généreux," pub. February 7, 1864; translation by Cat Nilan, 1999¹ (emphasis mine)
The astute may notice that Baudelaire begins by referring to the Devil as "she." Throughout the whole of the story, Baudelaire refers to the Devil as "he," except for the one paragraph containing the above excerpt. The reason, I think, is because in the paragraph in question, Baudelaire refers to the Devil as "Son Altesse," which is feminine despite being used for a masculine object. After this phrase, Baudelaire continues to refer to the Devil as "elle" until the preacher's quote, wherein the preacher says "il n'existe pas." Here, the Devil is "il" because (presumably) that's what the preacher said, and after this the Devil remains "il." Baudelaire uses "Son Altesse" once more in the short story, but there are no pronouns referring to the Devil before another masculine word ("personnage") is used to describe him.
A similar quote was said by Jim Carroll: "The Devil's greatest accomplishment was convincing the world he didn't exist."²
The most popular reinterpretation of this quote (the one the title of this node is taken from) is in the 1995 movie The Usual Suspects, written by Christopher McQuarrie. In it, Verbal Kint explains the story of Keyser Söze to the cop:³ (emphasis mine)
He is supposed to be Turkish. Some say his father was German. Nobody believed he was real. Nobody ever saw him or knew anybody that ever worked directly for him, but to hear Kobayashi tell it, anybody could have worked for Soze. You never knew. That was his power. The greatest trick the Devil ever pulled was convincing the world he didn't exist. One story the guys told me — the story I believe — was from his days in Turkey. There was a petty gang of Hungarians that wanted their own mob. They realized that to be in power you didn't need guns or money or even numbers. You just needed the will to do what the other guy wouldn't. After a while they come to power, and then they come after Soze. He was small time then, just running dope, they say...
1: "Le Joueur généreux" and Nilan's translation, available at: http://www.piranesia.net/baudelaire/spleen/29joueur.html
2: Quotations Page and Literature Page Forum: http://www.quotationspage.com/forum/viewtopic.php?t=1459
3: The Usual Suspects (script): http://www.godamongdirectors.com/scripts/usual.shtml