Taviani est un des experts modernes de l'histoire de Colomb. Il a laissé de nombreux ouvrages sur le sujet.
En 1931, alors qu'il était inscrit en première année à l'Université de Gênes, il lit un article de Roberto Almagna dans l’Archivio Storico della Scienza (Rome, 1926, p. 391.). Dans cet article le géographe italien indique : « Peut-être le problème de la conception et de la préparation du voyage de Colomb mériterait-t-il d'être examiné à nouveau... » Taviani va s'attacher au problème durant plus de quarante ans. Ce qui à l'origine était un sujet de distraction deviendra, au fil des ans, un des domaines d'expertise de Taviani.
Vers 1970, il commence à publier ses premiers ouvrages magistraux sur le sujet. Il participe à de nombreux échanges avec ses homologues espagnols et les chercheurs du monde entier. Taviani va visiter de nombreux lieux dans de nombreuses régions : en Ligurie, dans la région de Gênes; en Provence; en Corse; En Sardaigne; en Sicile; à Chio; à Tunis; en Portugal: à Lisbonne, Sagres, et Lagos; à Londres et à Bristol; en Espagne : à Palos de la Frontera, Moguer, Cordoue et Séville; à Galway en Irlande; en Islande : à Reykjavik, au Hvalfjörður, dans le Reyðarfjörður, à Akureyri; à Madère : à Porto Santo; aux Canaries; aux iles du Cap-vert; aux Açores; au Sénégal et à La Mina (Elmina) en Guinée.
Taviani a établi une liste de toutes les origines connues attribuées à Colomb. Il a eu l'audace de critiquer certaines de ces théories afin de les étudier à fond. De par ses fonctions universitaires et politiques il avait accès à toutes les archives historiques italiennes. Plusieurs de ses étudiants de l'université de Gênes se sont groupés autour de lui pour effectuer les recherches et les études. Il a abondamment commenté et documenté ses analyses.
À la lecture de ses travaux on constate que s'il existe des doutes réels dans l'origine génoise de Colomb, personne n'a jamais réussi ni à faire la preuve définitive du contraire, ni à prouver de manière incontestable une autre origine. Personne n'a jamais été en mesure de fournir des preuves authentiques indiscutables dans aucune des théories contradictoires connues.
Finalement on arrive à la conclusion que rien dans l'état des connaissances ne permet d'affirmer quoi que ce soit de définitif. L'origine de Christophe Colomb conserve la plus grande partie de son mystère.
Une inscription a été posée sur la maison attribuée à Colomb dans la ville de Gênes afin de rappeler le travail effectué par Taviani. Une plaque posée sur la maison après sa restauration indique : « In memoria di Paolo Emilio Taviani protagonista illustre della storia italiana e massimo esperto di Cristoforo Colombo ».