According a certain legend, Delcevo during Byzantine period was known as Vasilevo (on Greek - Tzar's village). Delcevo was first mentioned in a chapter of Serbian King Stefan Dušan between the 1347-1350 (14th century), and occured in connection with a land donation for the Lesnovo monastery.
The town of Delcevo has changed its name, several times.
During the Ottoman period Delcevo was visited by a Sultan. A large number of Christians converted to Islam, and at that time the town was called Sultania. The Islamised Christians have never learned the Turkish language and they renamed Sultania into their own language, Carevo Selo (Tzar's village). One year before Sultan Mehmed 2nd, the Turkish travel writer Evlija Čelebija had passed in Delcevo and wrote:
"After Vinica we climbed upon Kocani mountain meadow and after 4 hours walking along the ravine, we arrived in Carevo Selo. This is a Muslim village and it lays in the mountain ornamented with 100 houses and one marvelous mosque with minaret."
On May 8th, 1876 in the Razlovci village in the wider Delcevo disrict the local held a rebellion against the Ottomans, a rebellion lead by Dimitrija Pop Georgiev-Berovski and assisted by his father in law, a local priest named Stojan Razlovski. Unfortunatelly the rebellion was unsuccessful.
After the Russo-Turkish War, 1877–1878 much of the Delcevo Christian population left for Bulgaria and Turkish people from Asia moved in to and took their place.
During the Balkan Wars (1912-1913) most of the Turkish population left Delcevo, to that the number of inhabitants was leveled to 1,701. After these wars many Macedonians from the surrounding villages have settled the town (mostly from the villages Bigla, Selnik and Dramche, who bought the Turkish estates). In 1931 is recorded that Delcevo (Carevo selo) had 3,746 inhabitants.
Between the two world wars Delcevo was a small provincial town of dilapidated houses and a small number of craft shops with narrow muddy streets. In 1935 the first houses were built on the right bank of the Bregalnica river.