Le graphe de Barnette-Bosák-Lederberg est découvert par généticien Joshua Lederberg en 1965. Lederberg le construit en cherchant une contre-exemple minimal à la conjecture de Tait sur les graphes hamiltoniens, c'est-à-dire un graphe planaire non-hamiltonien étant 3-sommet-connexe. Lederberg émet l'hypothèse de sa minimalité mais est incapable de la prouver. Il démontre cependant qu'un contre-exemple minimal à la conjecture de Tait doit avoir strictement plus de 24 sommets.
A peu près à la même époque, D. Barnette et J. Bosák construisent six contres-exemples d'ordre 38 à la conjecture de Tait, redécouvrant indépendamment le graphe de Barnette.
Le graphe de Barnette-Bosák-Lederberg n'est pas le premier graphe de ce type puisque la conjecture de Tait, énoncée en 1884, est prouvée fausse dès 1946 par William Tutte qui construit alors un contre-exemple à 46 sommets, le graphe de Tutte. C'est cependant, lors de sa publication, le plus petit contre-exemple connu à la conjecture de Tait. En 1988, Holton et Brendan McKay prouvent sa minimalité et construisent les 6 seuls graphes d'ordre 38 étant des contre-exemple à la conjecture de Tait.
