How did the famous phrase Trick Or Treat come to be?

As recently as when I was a child (not long ago in the history of the world), there was an implied menace to the custom, at least in the U.S. The expression stood for a kind of extortion. It meant “Give us a treat or we’ll play a trick on you”—and it could result in some kind of mischief, not always innocent, such as papering your yard or soaping the windows of your car. I can remember my parents keeping nervous watch for roving boys who might be up to no good.

Meanwhile, the neighborhoods were deemed safe enough for little kids to go about in costume collecting treats without any adults accompanying them. Treats were often homemade, and there was no fear of harm or contamination. Life was simpler then.

The holiday itself, All Hallows’ Eve, is a very old one with its roots in ancient Celtic beliefs and superstitions. You can read one account of it here and find many others if you look around.

The phrase dates from the 1930s and, as @Jeruba said, originally had a neagtive connotation.

It started as a threat to fend off tricks such as overturning outhouses or soaping store windows, unless sweets were given out. In the US, it has become the most important holiday after Christmas. (on the list of holidays; the date of Halloween is before Christmas, obviously).

It was great! I mean, I got candy! Dressed up as a vampire killer or course. That’s all that matters, right? Getting loads and loads of candy?

Originally, the idea of going around and “begging” for treats at strangers doors, was to help souls get into heaven from purgatory. The kids would go around and essentially offer their prayers, if you paid them off with treats.

In modern times, as noted by others, children would get pretty PO’d if you didn’t give them anything, and they would often vandalize your home or possessions. Hence the term “Trick-or-treat.”