The first mention of Milejczyce dates back to the 15th century and talks about the presence of a settlement in this place - a spot where travelers could take some rest. The Royal Route to Brześć Litewski was located here.

In 1516 Milejczyce was granted a town charter under the Law of Magdeburg. Two parishes, an Orthodox and a Catholic one, were also set up at that time. At first, the town belonged to Troki province, then to Podlasie province, and since 1517, to the newly formed Brześć Province.
In the 16th century Milejczyce was quite a well developed town. There were a dozen or so taverns and many craftsmen’s workshops. The first synagogue was built in 1857. Two years later, a serious fire broke out in the town.

After World War I, Milejczyce lost its importance. Among other things, the town charter was taken away. In the interwar period, the town was an important holiday resort for Jewish people, who came here from all around Poland due to its forest microclimate. During World War II, a ghetto was set up here.