Le origini della Diocesi di Mantova non si possono definire con certezza storica. Secondo l'opinione più comune, esse risalgono all'inizio del sec. IX. Per il Savio, che accetta la costante tradizione mantovana, la città venne eretta a Sede Vescovile probabilmente nell'estate dell'804: Papa Leone III, venuto a Mantova su invito di Carlo Magno per verificare il ritrovamento del Preziosissimo Sangue, ne stralciò il territorio dalla Diocesi di Verona. La mancanza assoluta di documenti riguardanti la vita della nostra Diocesi prima del secolo IX convaliderebbe tale opinione.
Per Paolo Fridolino Kehr, invece, il Vescovado di Mantova dovrebbe risalire agli ultimi anni della dominazione longobarda (760 circa) e forse al sec. VII. Il primo documento storico che attesta l'esistenza di una Diocesi perfettamente sviluppata - una lettera scoperta dal Mai e "ab historicis mantuanis neglecta" - risale all'ultimo decennio del sec. VII o al primo decennio del sec. VIII. Mons. Fermo Lanzoni, sulla scia del Kehr, non ha difficoltà a portare l'esistenza della Diocesi di Mantova al sec. V o VI sulla scorta di argomentazioni di convenienza: soprattutto l'importanza storica e strategica di Mantova in quei secoli.
Le condizioni politiche e militari degli anni dell'ancora forte dominazione longobarda spiegano facilmente come la Chiesa di Mantova, all'epoca sotto dominio bizantino, non sia ricordata nei documenti contemporanei e come dai Sinodi Romani e dalle adunanze degli scismatici gradensi (Scisma dei tre capitoli) fosse costantemente assente il Vescovo di Mantova.
Mons. Paolo Guerrini conforta la tesi del Kehr con la "costante norma organizzativa che la Chiesa ha sempre seguito nel suo sviluppo": elevare, per prime, a sede vescovile, le città più lontane dalla sede metropolitana, che per Mantova era Aquileia. Così avvenne per Brescia, Torino e Verona.
Il Guerrini si riallaccia agli argomenti del Lanzoni modificando quelli del Kehr e in tal modo spiega la sconcertante mancanza di documenti come l'unanime attestazione degli storici mantovani (che pongono intorno al sec. IX la costituzione della Diocesi), ammettendo la scomparsa della sede vescovile negli anni dell'invasione longobarda.
Ciò era avvenuto per altre Diocesi limitrofe. Mantova, mal difesa dalle truppe bizantine, al dire di Paolo Diacono, fu presa nel 603 da Agilulfo e venne per metà distrutta. L'invasione barbarica sconvolse tutti gli ordinamenti sociali, politici ed economici. Anche le antiche circoscrizioni territoriali religiose furono rimaneggiate: la Diocesi di Mantova venne compartita fra quelle confinanti di Verona, Brescia e Reggio. A seguito dell'invasione franca, Mantova sarebbe stata "restituita" a dignità di sede vescovile: tale restituzione fu considerata erroneamente come prima costituzione in Chiesa autonoma o Diocesi.
Con gli scavi effettuati a partire dal 1958 nell'ambito del vecchio Seminario, particolarmente nella zona del refettorio e della cappella, vennero alla luce, a notevole profondità, tracce di un edificio ottagonale, ritenuto il battistero paleocristiano urbano, separato dalla chiesa esistente prima di quella romanica di S. Paolo. Si rinvenne pure una piccola parte di pavimento musivo, che non si dubitò di far ascendere al sec. IV o V della nostra era. Sono resti importanti, sufficienti a giustificare, se non l'affermazione, almeno la persuasione che già prima della sua distruzione da parte dei Longobardi Mantova fosse sede vescovile. Non è poi possibile tacere un argomento per ritenere Mantova sede vescovile costituita prima dell'inizio del sec. IX. Come concepire la sua scelta per il convegno dell'827, inteso a comporre il dissidio tra Aquileia e Grado, se essa fosse stata una città senza tradizione di autonomia e prestigio ecclesiali tali da far convergere in essa, oltre i presuli delle due circoscrizioni in lizza, anche diversi appartenenti alle province ecclesiastiche limitrofe dell'Italia Settentrionale.
Per tanti secoli la Diocesi di Mantova fu suffraganea di Aquileia. Il 13 aprile 1452 Nicolò V sciolse Mantova dalla giurisdizione aquileiense, dichiarandola immediatamente soggetta alla Santa Sede. Nel 1577, però, a seguito dell'invito rivoltogli dal Visitatore Apostolico Angelo Peruzzi, vescovo titolare di Cesarea e suffraganeo di Bologna, il Vescovo di Mantova Marco Fideli Gonzaga (+1583), salvi i privilegi concessi da Nicolò V, scelse di partecipare ai Sinodi Provinciali di Aquileia. Nel settembre 1803, in forza del Concordato tra Pio VII e Napoleone I, la Diocesi di Mantova fu dichiarata suffraganea di Ferrara: disposizione, però, mai attuata.
Il 19 febbraio 1820, infine, con Breve del medesimo Sommo Pontefice, che volle aderire alla richiesta della Corte Imperiale d'Austria, avvenne l'aggregazione di Mantova alla Provincia Ecclesiastica Lombarda. Da allora il suo metropolita è l'Arcivescovo di Milano.
Da data non precisa è Patrono principale della Città e della Diocesi di Mantova S. Anselmo (+1086), Vescovo di Lucca, la cui venerata salma incorrotta è conservata sotto l'Altar Maggiore della Cattedrale.