Page 169 of Science Fact and Science Fiction: An Encyclopedia, currently viewable on google books here, lists a number of early examples:
Early fictional treatments of evolutionist ideas often focused on the
relatedness of humans and apes, as in Thomas Love Peacock's depiction
of Sir Oran Haut-Ton in Melincourt (1817) and James Fenimore
Cooper's establishment of another simian species at the top of the
hierarchy of creation in The Monikins (1835). A. G. Gray Jr.'s "The
Blue Beetle" (1856) considered the broader implications of the thesis.
Alfred Lord Tennyson's In Memoriam (1850) conceded the strength of
Chambers' argument [referring to an earlier discussion on the page of
the pro-evolutionary nonfiction book Vestiges of the Natural History
of Creation from 1844], which were published midway through its
composition, while Benjamin Disraeli reacted against them in Tancred
(1847). There is a remarkable dream sequence in Charles Kingsley's
Alton Locke (1850), in which the hero experiences the entire evolutionary history of life on Earth, imagined in Lamarckian terms.
From the descriptions, Melincourt and The Monikins sound like fanciful tales of intelligent apes and monkeys, I'm not sure if they actually make any explicit suggestion that humans evolved from such ancestors. I don't know if evolution seen in a dream sequence would count as "treating evolution as scientific fact" in your view, and although dreams are inherently fantastical the overall story is not fantasy or science fiction, but if you would treat the dream chapter as a fantasy that does treat evolution as a fact then Alton Locke could be the first example of what you're asking for from the ones mentioned above, you can read it in Chapter XXXVI (36) here. Though if you count dreams, the philosophical dialogue D'Alembert's Dream by Denis Diderot from 1769 features a character who talks in his sleep and makes statements that seem to describe some form of evolution, which lead other waking characters to a discussion of evolutionary ideas (there's a good chapter on Diderot in Darwin's Ghosts: In Search of the First Evolutionists, a book on pre-Darwinian evolutionary ideas). For example:
MADEMOISELLE DE L’ESPINASSE: Then he began to babble something or
other about seeds, scraps of flesh minced and placed in water,
different races of animals which he saw in succession as they were
born and passed away. With his right hand he imitated the tube of a
microscope and, with his left, I think, the opening of a vase. He
looked into the vase through the tube and said, “Voltaire may make as
much fun as he likes about it, but the Eel-monger is right—I believe
my eyes, I see them—how many of them there are! How they come and go!
How they wriggle around! . . .” The vase where he was looking at so
many momentary generations he then compared to the universe. He saw in
a drop of water the history of the world. This idea appeared grand to
him. He found it entirely compatible with good philosophic practice,
which studies large bodies by examining small ones. He said, “In
Needham’s drop of water, everything takes place and goes away in the
blink of an eye. In the world, the same phenomenon lasts a little
longer, but what is our length of time compared to an eternity of
time? Less than the drop which I took up on the point of a needle
compared to the limitless space which surrounds me. An indefinite
succession of animalcules in the fermenting atom, a similar indefinite
succession of animalcules in the other atom which we call the Earth.
Who knows the races of animals which came before us? Who knows the
races of animals which will come after ours? Everything changes,
everything passes away. Only the totality remains. The world begins
and ends without ceasing. At every instant it is at its beginning and
at its end. It has never been anything else and never will be anything
else. In this immense ocean of matter, no single molecule resembles
any other, and no single molecule resembles itself for more than a
moment: Rerum novus nascitur ordo [a new order of things is
born]—there’s its eternal slogan.”
Science Fact and Science Fiction also says on p. 168 that the Compte de Buffon was another early speculator about evolution, and that "Buffon's ideas were, however, combined with those of Diderot for more adventurous literary exploration by Nicolas Restif de la Bretonne, whose La découverte Australe par un homme volant (1781) includes a detailed allegory of evolutionary development." (Though from the descriptions here and here it's not clear if it deals explicitly with evolution over time, or just shows a variety of alternate forms of people on different islands, though the first description does mention a 'lost race'.) The book Encyclopedia of Time discusses Restif de la Bretonne on p. 530, discussing another book he wrote that seems to involve evolutionary ideas: "He exploits a far-future setting with stunning originality, though without complete success, in Les Posthumes (1802). Here Restif portrays several million years of future history ... Biological evolution and vast geological changes, including the appearance of a second moon, are sketched as a backdrop for the life of Duke Multipliandre, a man born in the eighteenth century with the ability to project his mind into the bodies of other people and thus survive through succeeding eras to experience drastic social transformations along with changes in the human form." The book is available online here (in the original French). There seems to be a multi-page plot description of Les Posthumes in the book Origins of Futuristic Fiction by Paul Alkon, but unfortunately the key pages dealing with the far future are not available on google books.
In the original section I quoted, Science Fact and Science Fiction also mentioned The Blue Beetle, and p. 297 of Science Fiction: The Early Years, available on google books here, quotes a section from The Blue Beetle in which the narrator says "From the first inorganic atom which had received the force of life all other created beings had slowly, gradually, regularly advanced, up to the period in which I lived." From the plot description it sounds like the main story is about the creation of the titular blue beetle from an experiment trying to give life to inorganic matter, rather than evolution of one life form into another, though.
Another early example of evolution being treated as a scientific fact is mentioned in wikipedia's time travel article:
A clearer example of backward time travel is found in the popular 1861
book Paris avant les hommes (Paris before Men) by the French botanist
and geologist Pierre Boitard, published posthumously. In this story,
the main character is transported into the prehistoric past by the
magic of a "lame demon" (a French pun on Boitard's name), where he
encounters such extinct animals as a Plesiosaur, as well as
Boitard's imagined version of an apelike human ancestor, and is able
to actively interact with some of them.
This page has an illustration from the book showing these human ancestors:
This article from the journal Science Fiction Studies also mentions that Boitard had earlier written a book dealing with evolutionary themes, although it presented them by having the inhabitants of various planets represent various imagined stages in the evolution of humanity:
In 1839, 25 years before Verne, Pierre Boitard published the first
story of adventure and scientific popularization for young people:
Etudes astronomiques. This work depicts a voyage through the solar
system, with the beings of each of the planets representing a stage of
evolution: orang-outangs endowed with speech; fossil men (expressly
named as such); humanoids on Mars analogous to the African Black; and
modern men on Jupiter dressed as Romans. That was in 1839, in a
Christian review for families! Thus highly audacious SF appears in the
most unexpected institutions, to disappear soon after. (Two years
after his death, Boitard's Paris avant les hommes [1861] was
published; it is the first Darwinian narrative, and in it the
pre-historical ape-man makes his appearance.)
