"Everything starts as somebody's daydream. And, when you're daydreaming, it is science fiction. It's when you start work out how you put it together, true science fiction becomes real science."
- Larry Niven

As far as I know, the first reference to a pocket-sized telephone occurs in John Jones's Dollar by Harry Stephen Keeler, published in The Black Cat magazine in 1915; see the pocket wireless phone.

The British cartoonist W. K. Haselden described a "Pocket Telephone" and the cartoon was first published in The Mirror on March 5, 1919:

(The Pocket Telephone - When Will It Ring?)

See also these references; the telephonoscope from The Coming Race (1929) by JD Bernal and Heinlein's 1948 novel Space Cadet - the portable telephone.

Famously, Nikola Tesla was quoted in an interview in 1926 in Collier's Magazine:

"When wireless is perfectly applied the whole earth will be converted into a huge brain, which in fact it is, all things being particles of a real and rhythmic whole. We shall be able to communicate with one another instantly, irrespective of distance. Not only this, but through television and telephony we shall see and hear one another as perfectly as though we were face to face, despite intervening distances of thousands of miles; and the instruments through which we shall be able to do his will be amazingly simple compared with our present telephone. A man will be able to carry one in his vest pocket."

Just to put some historical perspective on this one, in 1964 the closest thing to a portable telelphone was a radiotelephone, which was typically the size of a couple of shoeboxes.

Bell System engineers made the first transatlantic radiotelephone call in 1915; it used huge towers and lots of power. The original VHF Squad Radios from WWII were originally designed to be used while riding a horse! The first cellular phones were demonstrated in 1973.

Present day radiotelephones may operate at any frequency where they are licensed to do so, though typically they are used in the various bands between 60 MHz and 900 MHz.