First time is mentioned in the ancient period, under it's ancient name Astibo, that occurs in connection with Peonia. Stip (Astibo) has its heritage in being the ancient capital of the Paeonian tribe who were situated in the western part of the fertile river Vardar basin around the 5th and 4th centuries BC. The two tribes that lived along the river Astibo, an estuary to the Vardar, were the Derrones, named after their god of healing, Darron, and the Laeaeans, who minted their own heavy coins as a sign of their sovereignty following the example of the Greek city-states on Chalkidiki. Although these tribes were heavily weakened by the Persian invasion of 480 BC, led by King Xerxes 1st, they remained a formidable power and a well-organized people, renowned for the production of their exceptionally heavy coins with emblems including domesticated specimens of the wild aurochs for which Paeonia was also famous. They were absorbed into the Macedonian empire by Alexander 1st before 360 BC.
The area itself is first mentioned in the writings of the historian Polien form the 3rd century BC, who talks of a river named Astibo which is presumed to be the river Bregalnica today. Polien also states that the Paeonian emperors were crowned in the vicinity of today's Stip. The first mention in written sources of a settlement in this area is from the time of the Roman emperor Tiberius 14-37 AD, when it is mentioned as an important settlement in the Roman province of Paeonia and the second stop on the Roman road from Stobi to Pautalia.
During the second half of the 3rd century BC the barbarian tribes, especially the Goths destroyed much of the northern settlements in the eastern part of the Roman Empire, among which Astibo as well. However, a new settlement - Estipeon - was soon founded on the same site which thrived though the late Roman and the Early Byzantine period.
When the Slavs came in the 6th-7th century AD, the city was renamed, it became Stip. the Slavic tribe of Sagudats permanently settled in this area, and gave the town its current name Stip. During the 10th century, the Saints Cyril and Methodius, after creating the first Slavic alphabet, came to preach to the Slavic tribes in this area before continuing their route to Great Moravia, thus the Slavic population from this area were the first Christians among the Slavs. The city was included in Tzar Samoil's medieval Macedonian state and after this came under the administration of a succession of conquerors. At the end of Samoil's reign, the city was conquered by the Byzantines; at the beginning of the 13th century, it was conquered by the Bulgarians, andthen, after the famous battle near Velebuzd, the city was conquered by the Serbian King Stefan Decanski.
There is little information about the development of Stip during Turkish occupation which would continue for the next five centuries, interrupted only during 1689-1690 when the city was liberated by the Austrians for two years. Finally in 1382, it fell under Turkish rule. The present city has retained many cultural monuments from different periods which give witness to the past of Stip.
During the Balkan Wars, Stip and the surrounding territory joined the Kingdom of Serbia. Events concerning the Kingdom of Serbia itself meant that Stip would shortly become a part of the Kingdom of Yugoslavia together with the rest of Vardar Macedonia. During the Second World War the Axis-allied Bulgarian forces occupied the city until 8th November 1944, after which it was captured by the Macedonian National Liberation Army. Because of this, Macedonia's modern republic recognises November 8th as "Liberation Day" in the city and municipality of Stip, it is thus a local holiday.