Wieś była początkowo własnością kościelną, a potem szlachecką. Leżała przy granicy Korony Królestwa Polskiego oraz Nowej Marchii. W 1361 preceptor zakonu joannitów Herman de Werborge nadał Hermanowi i Henrykowi braciom „de Banczen” oraz Ludekinowi „de Golcze” gród odnotowany jako castrum Machelin oraz wieś Machlino wraz z wsiami Brocz oraz Miłkowo. W 1364 Ludwik i Otto margrabiowie brandenburscy zapisali cesarzowi Karolowi IV Nową Marchię w jej granicach wymieniając m.in. Machliny. W 1552 wieś leżała w powiecie wałeckim Korony Królestwa Polskiego.

W końcu XV wieku wieś odnotowano w falsyfikacie z 1251 przy opisie granicy Korony z marchią. W 1564 przy opisie granicy Nowej Marchii z Polską jako punkt orientacyjny odnotowano dęby z naciosami stojące przy drodze machlińskiej, przy których zbiegały się granice wsi Pławno i Puszczy Studnickiej w Nowej Marchii oraz wsi leżących w Polsce Brocz i Machliny.

Miejscowość należała do szlacheckiego rodu Golczów. W 1554 Konrad Golcz zapisał swojej żonie Agnieszce Kleist po 400 grzywien posagu i wiana na połowach wsi Brocz, Klausdorf, Plumwerder, Rzepowo, Lubno, Machliny oraz na całym dworze w Broczu.