Origine formita el borda setlejo, Korneuburg estis dum jarcentoj kombinita kun Klosterneuburg sub la nomo Nivenburg (Niven-kastelo). La konekto estis vadejo trans la tiamaj riverbrakoj de Danubo. La latina nomo estis Corena Nova. En la jaro 1136 ĝi estis unue menciita en la ĉarto de la benediktanamonaĥejo Klein Mariazell [Klajn Mariacel], kiel nova foirplaco - novum forum, forum trans Danubium. 1268 ricevis Korneuburg la urban rajton de Duko Albrecht [Albreĥt] la Unua, kio kondukis al la formala disiĝo de Klosterneuburg.