Here are three examples of early stories with telepathy. The first, from 1889, is a perfect example of what we're looking for. It is antedated by Jules Verne's 1885 novel Mathias Sandorf as noted in b_jonas's answer; I mention it only in case there is some doubt as to whether there is real telepathy in Verne's novel. The second example, from 1871, is not a valid answer to the current question, because the telepaths use external devices (their staves), although some innate ability is needed to handle them; I mention it in case it may be useful to someone coming across this question in the future. The third example, from 1755, seems to be valid; however, telepathy is not a major theme, in fact is barely mentioned in this utopian story. All three examples were found with the aid of Science-Fiction: The Early Years by Everett F. Bleiler.
1889: "To Whom This May Come", a short story by Edward Bellamy, originally published in Harper's New Monthly Magazine, February 1889, which is available from the Cornell University Library; an 1898 reprint is available at Project Gutenberg. Here is Bleiler's review:
An island in the Indian Ocean. The protagonist is shipwrecked on an unknown island peopled by descendants of ancient Magi who were expelled from Asia. The unusual point about them is that they communicate by telepathy and that their vocal organs have almost completely atrophied. A few interpreters of mixed ancestry alone have partial power of speech.
Here is an excerpt from the story:
"It is you they understood, not your words," answered the interpreter. "Out speech now is gibberish to them, as unintelligible in itself as the growling of animals; but they know what we are saying because they know our thoughts. You must know that these are the islands of the mind-readers."
1871: The Coming Race (aka Vril: The Power of the Coming Race), an 1871 novel by Edward Bulwer-Lytton, available at Project Gutenberg. Plot summary from Wikipedia:
The novel centres on a young, independently wealthy traveller (the narrator), who accidentally finds his way into a subterranean world occupied by beings who seem to resemble angels and call themselves Vril-ya.
The hero soon discovers that the Vril-ya are descendants of an antediluvian civilization who live in networks of subterranean caverns linked by tunnels. It is a technologically supported Utopia, chief among their tools being the "all-permeating fluid" called "Vril", a latent source of energy that its spiritually elevated hosts are able to master through training of their will, to a degree which depends upon their hereditary constitution, giving them access to an extraordinary force that can be controlled at will. The powers of the will include the ability to heal, change, and destroy beings and things; the destructive powers in particular are awesomely powerful, allowing a few young Vril-ya children to wipe out entire cities if necessary. It is also suggested that the Vril-ya are fully telepathic.
The narrator states that in time, the Vril-ya will run out of habitable spaces underground and start claiming the surface of the Earth, destroying mankind in the process, if necessary.
The uses of Vril in the novel amongst the Vril-ya vary from destruction to healing. According to Zee, the daughter of the narrator's host, Vril can be changed into the mightiest agency over all types of matter, both animate and inanimate. It can destroy like lightning or replenish life, heal, or cure. It is used to rend ways through solid matter. Its light is said to be steadier, softer and healthier than that from any flammable material. It can also be used as a power source for animating mechanisms. Vril can be harnessed by use of the Vril staff or mental concentration.
A Vril staff is an object in the shape of a wand or a staff which is used as a channel for Vril. The narrator describes it as hollow with "stops", "keys", or "springs" in which Vril can be altered, modified, or directed to either destroy or heal. The staff is about the size of a walking stick but can be lengthened or shortened according to the user's preferences. The appearance and function of the Vril staff differs according to gender, age, etc. Some staves are more potent for destruction; others, for healing. The staves of children are said to be much simpler than those of sages; in those of wives and mothers, the destructive part is removed while the healing aspects are emphasised.
1755: A Voyage to the World in the Centre of the Earth: Giving an Account of the Manners, Customs, Laws, Government, and Religion of the Inhabitants, Their Persons and Habits Described ... : In Which is Introduced, The History of an Inhabitant of the Air, an anonymous booklet published in 1755; an abridged reprint from 1802, titled Bruce's Voyage to Naples, and Journey up Mount Vesuvius, is available at Google Books. It is the tale of a visitor to a utopian civilization inhabiting a 1000-mile-diameter globe inside the Earth. From Bleiler's review:
The humans are longhaired, bearded, and to some extent can read minds and character. They live to extreme old age, two hundred years not being unusual.
From the Google Books scan, p. 11:
"Know, O son of earth! that thou art not the first, by many, that chance has thrown upon our globe, neither is it impossible for us to visit your world: that god whom we truly adore has blessed us with those gifts that you are strangers to. We can, when we please, transport ourselves to your regions; and what surpasses even that, we have the gift of knowing the thoughts of those we converse with. By this means we are much better acquainted with your earthly brethren than you are yourselves, who can judge only by appearances. Often do you clasp that man to your bosom as a friend, who at the same time is your greatest enemy, and only professes friendship, while you have wherewithal to make him welcome; but when that fails, he will not only desert you, but leave you to starve in a dungeon, and pretend he never heard your name. These things, and worse, are common in your world: I have often made an excursion thither myself; and having the gifts I before mentioned, have seen things greatly unworthy of those beings that are, like ourselves, made after the image of our creator. Perhaps at a proper time I may tell you some particulars, but for the present we will confine ourselves to what relates to the world we are now upon, and which is in the centre of your globe."
From pp. 33-34, maybe an instance of telepathy in action:
I rose the next morning as soon as it was light and strolled about the town till breakfast-time; and when I came home, my landlady perceiving the perturbation of my mind, took every method in her power to alleviate my anxiety.
