Par pilsētas dibināšanas gadu tiek uzskatīts 1873. gads, kad pa jaunuzbūvēto Znamjankas—Mikolajivas dzelzceļa līniju caur Kazankas staciju izbrauca pirmā lokomotīve. Ciemats pie stacijas sāka veidoties pēc 1884. gada, kad Kazanka kļuva par mezgla staciju. Ciematu nosauca pēc zemes īpašnieka vārda par Kefaļinu (Кефаліне). 1901. gadā staciju pārdēvēja par godu citai muižniecei Olgai Doļinskai par Dolinsku. 1919. gadā ciematu pārdēvēja par Ševčenkovi (Шевченкове), bet 1923. gadā izveidoto rajonu pēc stacijas nosauca par Dolinskas rajonu. 1938. gadā Ševčenkovei piešķīra pilsētciemata statusu, bet 1944. gadā to pārdēvēja tagadējā vārdā. Kopš 1957. gada Dolinskai ir pilsētas statuss un līdz 2020. gadam tā bija rajona centrs.
Pilsētā atrodas vairāki pārtikas rūpniecības uzņēmumi, ievērojams dzelzceļa mezgls.