Raymond Z. Gallun's 1937 short story A Menace in Miniature uses the following method for creating an ultra-microrobot: build a beetle-size scarab robot and use it to build a scarab the size of a grain of sand. That scarab is used to construct an even smaller scarab. The process continues until the desired size is reached. This method is similar to the master/slave method proposed by Richard Feynman in 1959.
Greg Bear's novelette and later novel Blood Music is another early user of this trope, although the nanomachines were biological in origin. On the other hand, once you get down to nano-scales, the difference between organism and machine is very blurry. Nanotechnology also features in Bear's Queen of Angels, and its sequel, Slant.
The Monoliths in the 1982 book (and 1984 movie) 2010: Odyssey Two act like nanomachines, but are great big self-replicating machines. They turned the planet Jupiter into a star by igniting its core. The proper term for macroscale replicators are Von Neumann machines.
In Michael Crichton's Prey, a sentient swarm of nanomachines acts as the central premise, which starts to act in predatory manner.
In the satiric science-fiction novel, TIM, Defender of the Earth, one character uses the implications of nanotechnology to turn himself and the rest of Britain's population into a collective hive-mind.
The counterculture novel How to Mutate and Take Over the World ends with nanomachines transforming the entire world into key-lime pie filling.
In the second of the Thursday Next series of novels by Jasper Fforde, Thursday's inventing uncle Mycroft invents some nanomachines. Her time-traveling Chronoguard rogue father who does not exist in real time (that's a mouthful) eventually has to time travel to the beginning of life on Earth with the nanomachine colony (instructed to convert all organic material into Dream Topping) in his fist, to prevent the world ending in a sugary, confectionery manner. Turns out we are all evolved from Dream Topping. Which actually explains a lot.
The epilogue of Look to Windward by Iain M. Banks features an artificial shape-shifting assassin composed of "E-Dust" (Everything-Dust), originally intended as a building material but inevitably turned to darker purposes. The Culture in general seem to have progressed beyond nanotech, referring to "picofoam" as the building blocks of their AI Minds. "Picofoam complex" is the backup computational substrate for a mere ship drone's AI core, as described in Excession. Most of a true Culture Mind actually exists in hyperspace, where it may function unburdened by pesky nuisances like the speed of light and neutron decay.
The anti-Descolada virus designed by the heroes in the Ender's Game sequels. Ironically, the original Descolada virus counts too, as it was engineered by an unknown alien race as a terraforming agent.
The plot of the Moonrise and Moonwar by Ben Bova revolve around nanomachines. A subversion occurs when one character proposes making nanomachines that act like dust, to blind the invading army, and another character suggests just using dust instead.
Nearly-omnipresent nanotechnology is an important part of the setting and plot in Neal Stephenson's novel The Diamond Age (So named because with nanotech, diamond becomes literally as cheap as dirt, making it a useful building material.)
The eyves in Sergey Pavlov's novel Moon Rainbow aren't as much nanomachines as they are alien microorganisms, but they do grant people superpowers. Much of the book is devoted to exploring psychological and social consequences of this. In the sequel, though, they are just an excuse for the hero to kick some ass.
Nanomachines figure prominently in Nancy Kress's novel Beggars and Choosers (1994), the middle book of a trilogy beginning with Beggars in Spain (1993) and concluding with Beggars Ride (1996).
In Specials, the third book of Scott Westerfeld's Uglies series, it is revealed that the Specials have nanobots in their blood that allow them to heal faster than normal humans. Nanos can also be really bad, though, as in the scene where Tally and Shay end up destroying a museum by accidentally unleashing some. (This scene is referenced for comedic value in Extras, when Shay's solution to a problem is an excited cry of "Nanos!")Nanos are also what allow the Holes in the Walls to work like they do. In fact, nanos are everywhere in that world.
In the Nulapeiron Sequence (and the prequel, To Hold Infinity) by John Meaney, nanotech is considered rather crude and almost everything is instead done using 'femtotech', comprising 'engineered pseudatoms', whatever that might mean. References are even made to 'attotech', engineering using the fundamental building blocks of spacetime, referred to as Twistors.
In Ken MacLeod's Fall Revolution series, nanotech replicators and the creation of true AI lead to the singularity where many humans upload themselves to a computer framework and boost their intelligence and capabilities to godlike levels. The humans left behind in the solar system after the departure of the Fast Folk (so named due to the speed of their thought) use nanomechanical devices as the basis of much of their technology, the idea being that mechanisms are practically immune to subversion unlike their computer counterparts with corruptible software.
The Revelation Space series covers the collapse of much of human civilization following the spread of an alien disease which corrupts human technology in very unpleasant ways. The problem is compounded by the return of the Inhibitors, a vastly ancient machine race who use replicating technology hundreds of millions of years in advance of humanity which might be based on even smaller scale femtotechnology...
In Pushing Ice, many of the other inmates of the Spican's "zoo" have access to femtotechnology, again far in advance of the nanotechnology humans wield and correspondingly more dangerous when replicators run out of control. in something of a twist, it is suggested that much of the alien femtotech was in fact human in origin... thanks to time dilation humanity progressed significantly whilst the crew of the Rockhopper were in transit to the Spican structure.
Century Rain Earth was abandoned after nanomachines that were supposed to fix global warming start to eat everything to fuel themselves. The Slashers, who are a splinter human group, don't care if nanomachines caused problem in the past and continue to use them, and have them present in their blood.
In Bloom by Wil McCarthy, nanomachines have run amok and eaten the entire biosphere of Earth, plus spread out into nearby space. Human refugees survived by colonizing the outer solar system, including Jupiter's moon Ganymede. The novel's plot follows the first mission sent back sunward to find out what's left.
In the opening of John Ringo's Council Wars series 41st century humanity has reached the point where people have the power to transform themselves into all sorts of nifty things, up to and including sentient clouds of nanites. Which must have been a lot of fun... right up to the point where somebody turns off all the power.
In Ringo's Legacy of the Aldenata, the Galactic economy is based primarily on control of nanomachines used to build material from the atomic level up. With the new threat introduced in The Eye of the Storm, Mike O'Neal, Jr kicks this in the head, thanks to Darhel interference with the human forces supposedly defending against hostiles making them varying degrees of useless.
Luckily the Samothrace operative in Drakon has a small Fabber which can make whatever he wants, diamonds, components for Plasma rifles, anything small enough. The Draka he's chasing was caught in an accident so it doesn't have these luxuries, and it can think of better ways to commit suicide then use the enemy's weapons.
Quickies (or "shustrs" in original Polish text) are the mainstay of Lusanian society in Stanisław Lem's Observation on the Spot. They do everything, from providing energy and material wealth to enforcing laws of ethics as laws of physics. In Lusania "man" doesn't kill a "man" — the environment won't let him. They could even provide immortality, but those who tried it generally found that it wasn't worth the effort.
In his Peace on Earth nanomachines are also the ultimate stage of Mechanical Evolution of human weaponry.
Walter Jon Williams's novel Aristoi covers these, in various aspects, in great detail. Nanomachines are pretty much the basis for the entire economy, and a great deal of effort is expended in making sure the few people authorized to design new ones know what they're doing. The novel goes into more than usual detail on what it would take to actually get one running, including troubles such as getting rid of the heat such things would generate, especially in a vacuum. Gray goo does come up a couple times, at least once as a malicious attack.
The Plague Year Series details the effects of a devastating nano-tech plague which disassembles all warm-blooded life forms below 10,000ft elevation.
An entire manufacturing entity — Chasti Perma Lock has been created which produces nanite powered devices such as chastity devices, gags and so forth by the action of nanites on a person. For example, a chastity device is made by nanites closing up the ... operative ... opening permanently. You can use your imagination as to the rest.
The Days of Solomon Gursky by Ian McDonald. It starts in a near-ish future where nanomachines are routinely used to build virtually anything. Out of diamond if you like. And then the protagonist invents a process that uses nanomachines to entirely replace the cells in a living creature (such as a human). This essentially converts the creature into a new immortal form entirely constructed from nanomachines. The rest of the novella explores the full astounding ramifications of this over the following centuries and millennia.
Raymond Z. Gallun's 1937 short story "A Menace in Miniature" features human spacefarers being attacked by microscopic aliens flying microscopic machines against them. Unusually for an early nanotech story, Gallun also considers the limitations of such tiny machines, enabling the protagonists to develop defenses against them. Notable because it pre-dates Dr. Richard Feynmann's original concept of nanotechnology by 22 years.
In the Jacob's Ladder Trilogy, groups of nanomachines called colonies were created by Cynric the Sorceress. They are used for a variety of purposes, including granting Exalts their abilities and making physical bodies for the Angels.
The X-Files novel Antibodies revolves around these. A medical research facility is burned down by the conspirational elements within the US government because they managed to develop nanomachines that are able to cure any fatal disease and trauma within their host. This leads to Agents Mulder and Scully trying to find the one person who still has them before the the Conspiracy can.