Notts County začal pôsobiť v roku 1862. Klub vznikol ešte pred založením Futbalovej asociácie a na začiatku hral skôr klubový futbal ako futbalovú asociáciu. V čase svojho vzniku sa Notts County, podobne ako väčšina športových tímov, považoval za klub "len pre džentlmenov". Notts County sa považuje za jeden zo začiatočníkov súčasnej hry, dokonca sa mu pripisuje vynález ofsajdovej pasce[] . Notts County je najstarším profesionálnym futbalovým klubom na svete (v iných futbalových odvetviach sú staršie profesionálne kluby).
Klub hrával na začiatku v Park Hollow na Nottinghamskom hrade. V decembri 1864 sa rozhodlo, že klub bude hrať zápasy proti externým tímom, a rozhodlo sa, že si musí nájsť väčšie priestory. Po hraní na viacerých miestach sa The Magpies v roku 1883 usadili na Trent Bridge Cricket Ground.
Futbalová liga
V roku 1888 sa Notts County spolu s ďalšími jedenástimi futbalovými klubmi stal zakladajúcim členom Futbalovej ligy. Svoju prvú ligovú sezónu ukončili na jedenástom mieste. V sezóne 1890-91 dosiahli Notts County svoje historicky najvyššie umiestnenie v lige, a to tretie miesto, a o desať sezón neskôr skončili tiež tretí.
Finále pohára FA
25. marca 1891 sa Notts County po prvýkrát dostal do finále FA Cupu, ale nevyhral ho.
Notts County si to vynahradili v roku 1894, keď v Goodison Parku prvýkrát v histórii vyhrali FA Cup. Straky porazili Bolton Wanderers 4:1 a Jimmy Logan zaznamenal prvý hetrik v histórii finále FA Cupu. Notts County sa stal prvým klubom mimo najvyššej divízie, ktorý vyhral FA Cup - v tej sezóne skončil na treťom mieste v druhej divízii.
