L'histoire s'ouvre dans un château imaginaire de Westphalie — région d'Allemagne — présenté ironiquement comme le meilleur des châteaux
par le précepteur Pangloss, philosophe optimiste dont la doctrine — « tout est pour le mieux dans le meilleur des mondes possibles » — sera mise à l'épreuve tout au long du récit. Candide, jeune homme naïf élevé dans cet univers clos, en est chassé après avoir été surpris avec Cunégonde, la fille du baron. L'expulsion hors du château constitue le premier mouvement d'un voyage qui ne s'arrêtera plus.
Candide traverse d'abord la Hollande, où il retrouve Pangloss atteint de la syphilis et réduit à la misère. Les deux hommes embarquent ensuite vers Lisbonne, où ils arrivent au moment d'un tremblement de terre dévastateur — référence directe au séisme de Lisbonne de 1755, qui avait profondément ébranlé la pensée optimiste européenne. Candide assiste à un autodafé organisé par l'Inquisition, censé prévenir de nouvelles catastrophes, et voit Pangloss pendu. La vieille dame au service de Cunégonde, rescapée d'une vie marquée par d'innombrables malheurs, joue à Lisbonne un rôle de pivot narratif : c'est elle qui réunit Candide et Cunégonde.
Fuyant le Portugal, Candide, Cunégonde et la vieille dame s'embarquent pour Buenos Aires. Cunégonde y est retenue par le gouverneur, et Candide doit fuir vers le Paraguay, où les jésuites exercent un pouvoir temporel absolu sur les populations indigènes — Voltaire y livre une satire mordante de la colonisation religieuse. Candide y retrouve Cacambo, son nouveau compagnon, ainsi que le frère de Cunégonde devenu officier jésuite. Après avoir tué (involontairement) ce dernier, il s'enfonce dans la jungle sud-américaine, traverse le pays des Oreillons, puis parvient au Surinam — colonie hollandaise — où il rencontre un esclave mutilé dont le témoignage constitue l'une des charges les plus directes du conte contre l'esclavage et la colonisation.
Avant d'atteindre le Surinam, Candide et Cacambo découvrent l'Eldorado, pays imaginaire d'Amérique du Sud où règnent la richesse, la tolérance et le bonheur. Cette utopie fonctionne comme un miroir inversé du monde réel : ni guerres, ni tribunaux, ni pauvreté. Pourtant, Candide choisit de repartir — il veut retrouver Cunégonde et prouver sa valeur. Ce départ volontaire du seul lieu idéal du conte est lourd de sens philosophique : le bonheur offert sans effort ni travail ne satisfait pas l'être humain.
De Surinam, Candide s'embarque pour Bordeaux en compagnie de Martin, philosophe pessimiste qui devient son nouveau contradicteur intellectuel, en opposition symétrique avec l'optimisme de Pangloss. À Paris, Candide est victime des arnaques de la société mondaine et du monde littéraire — Voltaire y glisse une satire de la capitale. Il passe ensuite brièvement par les côtes anglaises, où il assiste à l'exécution d'un amiral — épisode inspiré de l'affaire du vice-amiral Byng — et formule la remarque cinglante selon laquelle en Angleterre il est « bon de tuer de temps en temps un amiral pour encourager les autres ». Il gagne ensuite Venise, où il était convenu de retrouver Cacambo et Cunégonde. Dans cette ville, il rencontre Pococuranté, noble vénitien blasé de tout, nouvelle figure de la satire voltairienne — cette fois contre l'indifférence et l'ennui des privilégiés.
Cunégonde et Cacambo se trouvent finalement à Constantinople (aujourd'hui Istanbul), où Candide rachète Cunégonde — devenue laide, selon le récit — ainsi que Pangloss et le frère de Cunégonde, retrouvés comme esclaves aux galères. Le groupe s'installe sur une petite propriété aux abords de la ville, où une rencontre avec un vieux paysan turc content de cultiver son jardin fournit à Candide la leçon finale : face aux maux du monde et aux illusions des grands systèmes philosophiques, « il faut cultiver notre jardin ».
Cet itinéraire n'obéit pas à une géographie réaliste mais à une géographie philosophique. Voltaire choisit ses étapes en fonction des cibles qu'il veut atteindre : la guerre (Westphalie, la bataille entre Bulgares et Abares), l'Inquisition (Portugal), le colonialisme et l'esclavage (Amérique du Sud), la corruption mondaine (Paris), l'absurdité militaire (Angleterre), le désœuvrement des élites (Venise). Le monde entier défile devant Candide comme une somme d'expériences désabusantes, jusqu'à ce que l'ultime sagesse du conte — modeste, concrète, anti-systématique — s'énonce dans un coin de jardin turc.