O narodení Paganiniho sa traduje legenda: Tri špinavé, napoly zrúcané schodíky úzkeho, krivolakého priechodu z ulice do ulice viedli do sivého domu v Passo di Gatta Mora. Povesť vraví, že na týchto schodíkoch sa raz skĺzla starena-pôrodná babka. Ako sa potkla, spomenula čerta. Vtom sa pred ňou otvorili dvere a ozval sa |piskľavý, mraučavý plač novorodeniatka. Bol to Paganini. Decko kričalo celú noc, až do rána. Plakalo, ako keby sa sťažovalo, že ho rodičia svojvoľne privolali do života tejto daždivej, búrlivej noci, keď vlny príboja udierali do oboch Janovských mól ako delové výstrely.
Paganini sa narodil v noci z 26. na 27. október roku 1782.
Ako malý bol škaredý: Hrával sa s deťmi ošklivý chlapček s vyčnievajúcou bradou, širokým čelom, kučeravými čiernymi vlasmi a veľmi dlhým nosom. V tejto mrzkej opičej tvári sa zvláštne vynímali ohromné achátové oči. Boli neobyčajne krásne a prekvapujúco kontrastovali s celkovým výzorom krivonohého decka, s jeho dlhými ramenami, veľkými chodidlami a dlhými prstami na dlhých rukách. Keď tieto oči zahoreli záujmom, tvár mu zjasnela a zaraz sa z nej vytratila všetka ošklivosť. No tento letmý obláčik sa rýchlo rozplynul a malý človiečik s vycerenými zubmi vyrážal divoké výkriky a nadávky, spolu s kamarátmi útočil na susedov a bil sa s nimi o loďky, ktoré rýchle plávali v špinavých mestských jarčekoch.
Keď v detstve ťažko ochorel a na dlhý čas sa ocitol bez spoločnosti rovesníkov, naučil sa hrať na lutne a otcovej gitare. Niccolov otec (signor Antonio) bol vášnivým hráčom – hazardérom. Raz začul Niccola hrať na lutne a to mu vnuklo myšlienku: — Budeš sa, Niccolo, učiť hrať na husliach. Urobím l teba zázrak, budeš zarábať veľa peňazí. Vieš, čo je to? Tieto husle patrili nášmu predkovi, pochovanému v Capue v kostole svätej Anny. Musíš na nich vyhrať to, čo som ja prehral na burze.
Potom začal syna učiť hrať na husliach. Malý človiečik ťažko chápal netrpezlivého učiteľa. Otec sa zlostil a na každú chlapcovu chybu odpovedal zauchom. Neskoršie vzal zo stola dlhé, hranaté pravítko a použil ho vždy, ked Niccolo urobil chybu. Údery boli ľahké, skoro nepozorovateľné, no spôsobovali na rukách krvavé podliatiny. Ked sa Tereza Paganini vrátila s nákupom, bol signor Antonio už celkom rozzúrený. Zatvoril chlapca do komory a prikázal mu hrať prvé cvičenie.
Rodina sa neskôr odsťahovala do Cremony v severnom Taliansku. Otec neustále Niccola mučil a trápil hladom.