Semasa awal Zaman Pertengahan, terdapat perubahan politik dan demografi yang besar di kawasan yang dimiliki oleh Montenegro hari ini.Semasa abad ke-6 dan ke-7, Slav, termasuk Serbia, berhijrah ke Eropah Tenggara.Dengan penghijrahan puak Serbia, negara serantau pertama telah diwujudkan di kawasan yang lebih luas Dalmatia purba, Prevalitana dan wilayah bekas lain: Duklja, Travunija, Zahumlje dan Neretlja principalities di kawasan pantai dan Principality of Serbia di pedalaman.Semasa awal Zaman Pertengahan, separuh selatan Montenegro hari ini adalah milik wilayah Duklja, iaitu Zeta, manakala separuh utara adalah milik Kerajaan Serbia ketika itu, yang diperintah oleh dinasti Vlastimirović.Pada masa yang sama, bahagian paling barat Montenegro hari ini adalah milik Travunia.