According to a comment by the OP, the earliest of the stories listed here that satisfies his criteria is "Brain Leeches" from Astounding Stories, July 1935. If you have one from before July, 1935, please post an answer. Stories rejected by the OP are indicated with a question mark.
1955: "By a Fluke" by Arthur Porges. Thoughts of an intelligent liver fluke.
1950 (?): "Strange Exodus" by Robert Abernathy; first published in Planet Stories, Fall 1950, available at the Internet Archive. Humans travel to the stars as parasites in gigantic space worms.
1939: "Discord in Scarlet" by A. E. van Vogt, proposed in Ram's answer; first published in Astounding Science Fiction, December 1939, available at the Internet Archive. Incorporated in van Vogt's 1950 fix-up novel The Voyage of the Space Beagle which has a Wikipedia page.
1936: "The Pygmies of Phobos" by Ralph Robin. From E. F. Bleiler's review in Science Fiction: The Gernsback Years:
Ages ago, two forms of intelligent life arose on Mars, humanoid creatures much like mankind and protozoa about a millimeter across. Both peoples developed mechanical civilizations at about the same time. When they became aware of each other, however, they immediately began wars of extermination. [. . .] Finally, after thousands of years of war, the peoples made a shaky peace. The protozoans, fearful that war would break out again, made a suggestion that satisfied both races: encasing Phobos in a shell to retain necessities of life and leaving the protozoans there, leaving Mars to the humans. [. . .] At this point, the protozoan dictator Thakin proposed an invasion of Mars. The council rejected this proposal with horror, but Thakin, gathering his followers and seizing the entire planetary supply of thorium, fled to Mars. There, he inserted individual protozoa into the brains of Martians, subjecting them to protozoan control.
[This one definitely counts: macroscopic brain parasites.]
1935 (?): "Parasite Planet" by Stanley G. Weinbaum, described in this Q & A; it has a Wikipedia page and is available at Project Gutenberg Australia. [Per a comment by the OP, fungi don't count.]
1935: "Brain Leeches" by Edward S. Mund; first published in Astounding Stories, July 1935, available at the Internet Archive. From E. F. Bleiler's review in Science Fiction: The Gernsback Years:
The beings on the spaceship close in the immediate area with a force screen of sorts and herd in the two young men. Near the spaceship, Jack encounters humans, and learns from them that the aliens are amoeboid puppet-masters who use humans as carriers. As Jack learns from a captive young woman from another planet, who either speaks English or is a telepathic broadcaster, the monsters, who are few in number, control their "steeds" by inserting tentacles up into their brains. Jack also learns from the monsters, one of whom rides him, that they plan to spawn and take over the Earth.
[I think this one counts. It's not completely clear from the review, but the aliens seem to be macroscopic ("amoeboid"), and if they are not living inside or permanently attached to their "steeds", at least they have their tentacles embedded in the steed's brain.]
1933 (?): "The Purple Brain" by Hal K. Wells; first published in Astounding Stories, December 1933, available at the Internet Archive. From E. F. Bleiler's review in Science Fiction: The Gernsback Years:
Neil Andrews and John Kincaid, while out horseback riding in the hills, encounter a cougar that has something on its head—a purplish, lumninescent jelly-like object that emits a feeling of overwhelming horror and cosmic evil. Kincaid shoots at the cougar, whereupon it springs away, while the two men are thrown from their panic-stricken horses. * Kincaid is not altogether ignorant of the monster, for he has heard tales according to which it is associated with the lodge occupied by the scientist Yaagir. * On proceeding to Yaagir's place, they are captured by the strange being, which now occupies a monstrous cadaver formed by combining two human bodies. The creature explains: Arriving from the planet Zaas, which is about six light-years away, it is a scout investigating the Earth and mankind. It will report back to Zaas, whereupon a huge fleet will come to Earth and conquer it, enslaving mankind as carriers for the jelly beings. As the two men can see from corpses lying about, the creature removes the top of the cranium, then infiltrates the brain. While the men watch in horror, the jelly being vivisects a couple of other captives, using a cosmic ray apparatus that both removes tissue and records the results photographically. [. . .] Not one of Wells's better stories, but perhaps the earliest instance of the puppet-master motif.
[I guess this one doesn't count. Apparently the jelly being only inhabits corpses, so not a parasite.]
1930 (?): Last and First Men by Olaf Stapledon has a Wikipedia page and is available at Project Gutenberg Australia. Stapledon's Martian invaders are cloudlets of ultramicroscopic units communicating telepathically to form a "group mind", a term apparently coined by Stapledon. In the Fifth Men the Martian units became parasites, conferring telepathic ability:
In sensory equipment, the new man was to have all the advantages of the Second and Third Men, and, in addition, a still wider range and finer discrimination in every sense organ. More important was the incorporation of Martian units in the new model of germ cell. As the organism developed, these should propagate themselves and congregate in the cells of the brain, so that every brain area might be sensitive to ethereal vibrations, and the whole might emit a strong system of radiation. But care was taken that this "telepathic" faculty of the new species should remain subordinate. There must be no danger that the individual should become a mere resonator of the herd.
[This example probably doesn't count. The original free-living Martians who invaded Earth had hive minds, but as parasites they may have been mindless.]
1923 (?): "Fungus Isle" by Philip M. Fisher, Jr., described in this old Q & A; first published in Argosy All-Story Weekly, October 27, 1923; reprinted in Famous Fantastic Mysteries, October 1940, which is available at the Internet Archive. [Per a comment by the OP, fungi don't count.]
1907 (?): "The Voice in the Night" by William Hope Hodgson, also described in the same old Q & A, is available at Project Gutenberg Australia and Librivox. From E. F. Bleiler's review in Science Fiction: The Early Years:
Somewhere in the North Pacific, the narrator who is fogbound on a
small vessel, is hailed by an unseen man in a rowboat. The
circumstances are suspicious, particularly when the stranger, who asks
for food, will not come close to the ship and insists that the lights
be extinguished. But the compassionate sailors float a box of supplies
to him. Some time later the invisible rower returns and tells his
story from out of the fog. Victims of a shipwreck, he and his fiancee
have been living on a nearby island that is covered with fungi. The
fungus is not only omnipresent, but some examples are shaped like
trees and humans. The narrator and his fiancee tried to avoid the
fungus, but after a time observed that it was sprouting on them. There
was nothing they could do, for even carbolic acid would not kill it.
When their food was nearly gone, they yielded to temptation and began
to eat the fungus, though with strong feelings of guilt. They do not
expect to live long. As the stranger moves away, the fog lifts for a
moment, and the sailors see what seems to be a blob-shaped fungus in
the rowboat.
[Per a comment by the OP, fungi don't count.]
