Le point de départ de Salammbô est la guerre des mercenaires contre Carthage racontée par l'historien grec Polybe. Mais le récit de cette « guerre inexpiable » tient en quelques pages et tout est à reconstruire. Flaubert rassemble une importante documentation. En mai 1857, il écrit à Jules Duplan : « Quant à moi, j’ai une indigestion de bouquins. Je rote l’in-folio. Voilà cinquante-trois ouvrages différents sur lesquels j'ai pris des notes depuis le mois de mars. » Outre ses lectures en bibliothèque, il interroge, par lettres, des spécialistes de l'Antiquité, et part visiter la Tunisie. Plus proche de lui, les écrits de Chateaubriand, notamment Les Martyrs, l'inspirent.
Lors de la parution du roman, Guillaume Froehner, archéologue et rédacteur à la Revue contemporaine, critique violemment la reconstitution historique et le style outrancier de Flaubert : « M. Flaubert, malgré ses efforts, ne montre pas une plus grande exactitude quand il nous trace la topographie de la ville ; ses inventions mêmes trahissent son inexpérience des choses de l'antiquité. […] Il n'y a presque pas de page où l'auteur ne s'efforce ainsi d'outrer la nature, et d'imprimer de rudes secousses à notre système nerveux » (article publié le 31 décembre 1862). Flaubert lui répond point par point dans un article publié le 24 janvier 1863 dans L'Opinion nationale. Il insiste sur le fait que Salammbô est un roman et non un ouvrage d'archéologie ou d'histoire.