Le comté de Notts a vu le jour en 1862. Le club a été créé avant la Football Association et, au début, on jouait un jeu avec des règles de club, plutôt que du football d'association. À ses débuts, Notts County, comme la plupart des équipes sportives, était considéré comme un club "réservé aux hommes". On pense que Notts County est l'un des précurseurs du jeu actuel, étant même crédité de l'invention du piège à hors-jeu []. Notts County est le plus ancien des clubs de football de l'association professionnelle du monde (Il existe des clubs professionnels plus anciens dans d'autres codes du football).
Au début, le club jouait au Park Hollow du château de Nottingham. En décembre 1864, la décision fut prise de jouer des matchs contre des équipes extérieures, et il fut décidé que le club devait trouver un lieu plus grand. Après avoir joué à plusieurs endroits, les Magpies s'installent au Trent Bridge Cricket Ground en 1883.
Ligue de football
En 1888, le comté de Notts, ainsi que onze autres clubs de football, est devenu un membre fondateur de la Football League. Ils ont terminé leur première saison de ligue à la onzième place. Notts County a obtenu sa meilleure place en 1890-91, et a également terminé troisième dix saisons plus tard.
Finales de la Coupe de la FA
Le 25 mars 1891, le comté de Notts atteint pour la première fois la finale de la FA Cup mais ne la remporte pas.
Le comté de Notts s'est rattrapé en 1894, lorsqu'il a remporté la FA Cup à Goodison Park pour la première fois de son histoire. Les Magpies ont battu les Bolton Wanderers 4 à 1 et Jimmy Logan a marqué le premier triplé de l'histoire de la finale de la FA Cup. Notts County est devenu le premier club en dehors de la première division à remporter la FA Cup - ils ont terminé à la troisième place de la deuxième division cette saison-là.
