The history of Mielnik Land as a separate unit begins in the 1530s, when it was carved out of Drohiczyn Land. Until the Union of Lublin, the province of Podlasie was part of the Grand Duchy of Lithuania; in 1569 it was transferred to the Kingdom of Poland. Local sejmiks for Mielnik Land took place at Drohiczyn, where two envoys were selected to the WarsawSejm.
Mielnik Land was not divided into counties. It had two royal towns, Mielnik and Łosice, both were residences of the starostas. Other towns of the province were Siemiatycze, NiemirówHorodyszcze and Rossosz. The town of Mielnik had a royal castle, in which on October 23, 1501, the Union of Mielnik was signed.