La urbo fondiĝis en 1686, sed jam en 1650 en insulo sur delto de la rivero Aidar establiĝis ŝirmejo de la sudaj limoj de Rusio kaj oni konstruis lignan preĝejeton.
En 1686 cele de plifortigo de la sudaj limoj de Granda Rusio ekestis militista tendaro Belsky.
Starobilsk estis ĉefurbo de Ukrainio dum kelke da tagoj dum la dua mondmilito kaj la unua urbo liberigita de germanoj.
En la jaroj 1939-1940 sur la areo de estinta monaĥejo estis militprizono por poloj, oficiroj (ankaŭ substandardistoj) de konstanta servo kaj rezervo de Pola Soldataro, prenitaj al soveta mallibero post okupo de Orientaj Limregionoj, post la 17-a de septembro 1939. Inter la 1-a ĝis 4-a de novembro ĉiuj polaj militkaptitoj estis dislokitaj en sovetaj urboj Kozelsk kaj Starobilsk, funkciuloj de polico, limgardistoj kaj prizongardistoj en Ostaŝkov. La 15-an de novembro 1939 en militprizono restis 3 946 polaj militistoj. Aprile kaj maje 1940 ili estis murditaj en la sidejo de NKVD en Ĥarkovo de lokaj funkciuloj kaj NKVD-laborantoj alvenintaj de Moskvo laŭ decido de Politburoo de la Centra Komitato de Komunista Partio de Sovetunio. Enterigitaj en Pjatiĥatki. 48 poloj mortis en la internigejo kaj estis enterigitaj en malnova urba tombaro, en 1995 oni transportis iliajn korpojn al ĉmira tombaro.
La 15-an de aŭgusto 1940 militkaptitoj provis muzikumi kaj kanti okaze de la Festo de Pola Soldato, sed ne eblis;
La 25-an de oktobro 1940 NKVD en interna korespondado anoncis bruligon de personaj dokumentoj de polaj oficiroj el la militprizono.
La 11-an de novembro 1940 en la militprizono okazis kunveno kun partopreno de generalo Jerzy Wołkowicki, kie majoro Ludwik Domoń vortigis flamantan alparolon en la Nacia tago de sendependeco — sovetaj politikaj gvidantoj malpermesis pluajn elpaŝojn.