Varšuvos kunigaikštystės egzistavimo laikotarpiu ši teritorija priklausė Sedlcų departamentui. Žlugus kunigaikštystei, departamentas buvo pervardintas į vaivadiją. Vaivadija pavadinta Palenkės vardu, nors tik nedidelė šiaurvakarinė vaivadijos dalis priklausė istoriniam Palenkės regionui. 9 buvusio demartamento apskritys (pavietai) sugrupuotos į 4 apygardas: