Th "first" Göteborg wasn't located where the Göta river (from which Göteborg takes its name (literally, fortress by Göta river)) debouches into the sea, which is where it is today, but much further up the river. This town was called Lödöse in medieval times.
By 1473 this very successful town had to move, so as to evade the tolls the Norwegians had placed between the mouth of Göta river and Lödöse. The new town was constructed much further down the river and called Nya Lödöse (New Lödöse), quickly shortened to Nylöse.
In 1619 the present city of Göteborg was founded and Nylöse was supposed to be abandoned in favour of the new city located only a couple of miles down river (i.e. even closer to the sea). However, quite a few of the burghers refused to move, and informally "New Lödöse" became Old Town (Gamlestaden). Gamlestaden is however archived under the old, correct name of Nylöse.
In 1951 the parish of Nylöse formed two districts (while still remaining one parish), Nylöse and Gamlestad. In 1969 the Gamlestad district of Nylöse parish formed the new parish of Sankt Pauli - the Nylöse district of Nylöse parish went back to being just Nylöse parish.
Oh - just to confuse things: the old town of Lödöse is still there, but of course nowadays reduced to a mere village. But the museum there is quite good.