6 июня 1919 года он вступил в Красную армию. В 1919–1920 годах принимал участие в Гражданской войне на Западном фронте в должности командира взвода. В марте 1921 года участвовал в подавлении Кронштадтского восстания. После войны Старостин в течение двух лет командовал ротой. В 1925 году он окончил артиллерийское отделение объединенной военной школы. В 1925–1932 годах командовал батареей и дивизионом. Затем в течение пяти лет занимал должность начальника штаба артиллерийского полка, в 1937—1939 годах — командовал полком. В 1939 году Старостина назначили начальником артиллерии 49-й стрелковой дивизии 3-й армии Белорусского Особого военного округа, а 4 июня 1940 года ему было присвоено звание генерал-майора. В марте 1941 года Старостина назначают начальником артиллерии 11-го механизированного корпуса. Награжден орденом Красной Звезды (1938).
113-я стрелковая дивизия начало войны встретила в составе 5-го стрелкового корпуса 10-й армии Западного фронта. 23 июня в боевом распоряжении командующего войсками фронта генерала Павлова командующему войсками 10-й армии говорилось: «Найти, где 49-я и 113-я стрелковые дивизии, и вывести». То есть и на второй день войны связи с дивизией, которой командовал генерал Алавердов, не было. Предположительно 113-я дивизия уже на второй день войны находилась в окружении и в течение последующих нескольких дней полегла на поле брани у поселка Семятичи. Сам командир соединения генерал Х.Н. Алавердов был взят в плен 1 июля 1941 года, при попытке выйти из окружения.
29-я моторизованная дивизия 23 июня 1941 года развернулась на фронте Кузница — Сокулка для прикрытия левого фланга своего 6-го механизированного корпуса 10-й армии. 25 июня она своим правофланговым 128-м мотострелковым полком в районе Кузницы вступила в бой с подошедшей 162-й пехотной дивизией противника. Не выдержав атаки пехоты противника, усиленной артиллерией, полк отступил на линию Номики — Заспиче. В дальнейшем 29-я дивизия прикрывала находящиеся в тылу части 27-й стрелковой дивизии и сосредоточение за ее левым флангом 6-й кавалерийской дивизии 6-го кавалерийского корпуса. И если еще днем 26 июня 29-я дивизия продолжала удерживать свои позиции, то к концу дня была оттеснена противником. В июле она попала в окружение в районе Гродно — Белосток — Минск. Например, вот что вспоминал инструктор пропаганды 106-го полка 29-й мотодивизии В.Е. Фролов о событиях, произошедших 29 июня 1941 года: «…В районе местечка Деречин — прорыв с боем. Тут была настоящая мясорубка. Помимо нас, тут собралось разных частей около 15 тысяч человек. Всю ночь, окружив, нас расстреливали в упор, давили танками, и немногие в эту ночь остались в живых. Шли на восток, собирались снова и шли с надеждой прорваться к своим». 17 июля 1941 г. командир 29-й мотодивизии генерал И.П. Бикжанов, переодевшись в гражданскую одежду, с группой офицеров двинулся на восток. Но уже 25-го числа у деревни Заболотье, под Бобруйском, был взят немцами в плен. Свои документы и форму он предусмотрительно зарыл в земле.
Когда в конце июня танковые группы противника отрезали пути отхода двум армиям Западного фронта, отходившим от Гродно и Белостока, войска этих армий, а также части 6-го кавалерийского корпуса 10-й армии, были окружены в районе Налибокской пущи. Те, кто не погиб, мелкими группами выходили из кольца через Неман и Березину в Полесье. Командир 6-го кавкорпуса генерал И.С. Никитин, будучи тяжело раненным, практически в бессознательном состоянии был захвачен в плен.
4-я танковая дивизия 6-го мехкорпуса 10-й армии в течение всего дня 23 июня 1941 года, выполняя противоречивые приказания вышестоящего командования, совершала бесконечные марши… Утром 24 июня она наконец-то перешла в наступление, но в результате тяжелого боя была остановлена на подступах к Гродно. На следующий день 4-я дивизия уже отходила за Свислочь. Как пишет А.В. Исаев, «на контрударе под Гродно история 4 тд не закончилась. Она приняла активное участие в попытках прорыва из “белостокского котла”. 4 тд пыталась прорвать немецкую оборону на рубеже реки Зельвянки южнее Зельвы. Отчаянные и достаточно организованные атаки прорывавшихся из окружения под Белостоком советских войск заставили командование немецкой группы армий “Центр” на несколько дней задержать на рубеже ряд соединений 2-й танковой группы Г. Гудериана. 30 июня стало последним днем организованных попыток прорыва под Зельвой». Командир 4-й танковой дивизии генерал А.Г. Потатурчев был взят в плен в гражданской одежде в Бобруйске. Его выдал предатель, бывший вольнонаемный из тыла дивизии, предложивший на время укрыться и подлечиться в доме своего родственника.
