Il vicariato apostolico di Essington, nella penisola di Cobourg, fu eretto il 6 maggio 1845 con il breveUniverso dominico di papa Gregorio XVI, ricavandone il territorio dall'arcidiocesi di Sydney. La missione in queste terre del nord era stata fondata dal missionario italiano Angelo Confalonieri, il primo prete cattolico a raggiungere il nord dell'Australia.[1]
Il vicariato apostolico fu dato in amministrazione ai vescovi di Perth, finché, due anni dopo, il 25 giugno 1847 fu elevato a diocesi con il nome di diocesi di Victoria, in virtù del breve Apostolici muneris di papa Pio IX.[2] Originariamente era suffraganea dell'arcidiocesi di Sydney.
Attorno al 1880 i gesuiti della provincia austriaca erano stati incaricati di istituire una missione allo scopo di evangelizzare gli aborigeni; circa sedici membri dell'ordine si dedicarono a questa missione e furono istituite stazioni missionarie a Rapid Creek, sette miglia a nord-est di Palmerston, Daly River e Serpentine Lagoon. Nel 1891 c'erano circa 260 cattolici nella missione. Tuttavia il lavoro non prosperò e dopo circa venti anni i gesuiti si ritirarono. Al loro ritiro la diocesi fu amministrata dal vescovo William Kelly di Geraldton.
Nel 1885 la diocesi si ampliò, incorporando la parrocchia di Thursday Island, che era appartenuta al vicariato apostolico del Queensland (oggi diocesi di Cairns).
Il 10 agosto 1888 assunse il nome di diocesi di Victoria-Palmerston.[4]
All'inizio del Novecento la diocesi fu affidata ai Missionari del Sacro Cuore di Gesù, e nel 1906 padre Francis-Xavier Gsell fu nominato amministratore della diocesi, con il titolo di prefetto apostolico.[5]
Il 29 marzo 1938 per effetto della bollaQuo commodius ha incorporato le isole australiane che erano appartenute al vicariato apostolico di Papuasia (oggi arcidiocesi di Port Moresby) e ha assunto il nome attuale.
Il 14 febbraio 1967 ha restituito la parrocchia di Thursday Island alla diocesi di Cairns.
Cronotassi dei vescovi
Si omettono i periodi di sede vacante non superiori ai 2 anni o non storicamente accertati.
Sede amministrata dai vescovi di Perth (1845-1847)
^Palmerston era il nome originario dell'odierna Darwin. Nelle fonti si trova sia la dicitura "Victoria-Palmerston" che quella di "Victoria e Palmerston".