In the 4th century Maleshevo was part of the state of Philip and Alexander the Great. After the disintegration of their empire, Macedonia as well as Maleshevo became part of the Roman province of Macedonia. In the 6th and 7th century, Slavs settled on the territory of Maleshevo. On the territory of Maleshevo, Konstantin Filosov composed the Cyrillic alphabet. With the disintegration of the Macedonian Samoil Empire, Maleshevo fell under Byzantine rule.
The name Maleshevo is mentioned for the first time in the written sources in the letter of the Byzantine emperor Basil II in which he talks about the number and composition of the dioceses of the Ohrid Archbishopric. One hundred years later Maleshevo is mentioned by the Arab travel writer Idrisi. Some scholars, such as Gae Cer, believe that in the 9th century the bishopric of Morozvizd (Morodvis) was transferred to Maleshevo, a city located along the upper reaches of Bregalnica, in the embrace of century-old beech and pine forests, which according to the weight of Basil II is from Maleshevo and Pijanec.
Maleshevo became part of the medieval Serbian state in 1334, then it was part of the fief of Konstantin Dejan and it is assumed that in 1394 the city of Malesh was destroyed by the Turks.
After the Balkans and the First World War, Maleshevo became part of the Kingdom of SHS from 20.05.1920.
Today Maleshevo as a geographical term covers an area of about 80,560 m2 and covers two municipalities – Berovo (town of Berovo and the villages Rusinovo, Vladimirovo, Ratevo, Dvorishte, Smojmirovo, Machevo, Budinarci and Mitrashinci) and Pehchevo.