Улица названа в честь органов правопорядка - милиции (от лат. militia - «войско»).

Изначально словом милиция было принято обозначать, нерегулярные вооружённые формирования, используемые в том числе и для поддержания общественного порядка, формируемые из добровольцев и не входящие в состав официальной системы государственных правоохранительных органов.

Термин милиция начали употреблять ещё в Российской Империи. По историческим данным первый раз он употребился в 1146 году и значился народным ополчением из местного населения, во времена смуты.

Основные функции милиции - поддержание признаков государства; защита прав граждан и общества. Милиция представляет собой систему государственных органов исполнительной власти, выполняющих функции поддержания порядка и стабильности в стране, области, регионе.^[17]

Известно, что первое название улица носила – Солдатская.

Согласно плана города за 1913 год улица Солдатская располагалась между улицам Сенная (ныне – улица Зинченко) и Мясного переулка (ныне – улица Можайского) и располагалсь параллельно им. Начиналась улица от Окружного суда и заканчивалась у реки Ингул. Позже улицу сократили.

Можно предположить, что в 1937 году на честь основания 20 лет милицииИнформация10 ноября 1917 года был принят Декрет НКВД «О рабочей милиции». Именно этот день до сих пор отмечается в России как «День милиции». улицу переименовали. Теперь мы знаем ее как улицу 20-лет Милиции, которая расположена в Подольском районе.

Протяженность улицы составляет около 665 метров. Просмотреть список протяженности всех улиц можно здесь.