© Андрей Парамонов (Харьков)

Во второй половине XVIII столетия за Дмитриевской церковью располагалось приходское кладбище, которое распространялось аж до Холодной горы, закрытое в начале XIX столетия. На его месте по плану 1822 года была спланирована площадь, которая получила в 1830-е годы имя Жандармской, от расположения на ней жандармской команды города Харькова. Здесь были жилые помещения для неженатых рядовых, кухня, конюшни, огороды, относящиеся к ведению этой команды. На площади также разместили и 3-ю полицейскую и пожарную часть, которую и сегодня украшает пожарная каланча. Северную часть бывшего Дмитриевского кладбища готовили по плану 1822 года под постройку нового здания Острога, отчего она получила имя Тюремной. В советское время она носила имя Красного Пожарника, в настоящее время – застроена и частично занята сквером Пожарников.

Пограничная улица, которая была продолжением Тюремной площади до Чеботарской улицы получила первоначально имя Тюремного переулка. Сформировался этот переулок в начале 1840-х годов и впервые был обозначен на плане города 1846 года. Наименование он получил естественно от тюремного замка, расположенного на Тюремной площади и выходившего и на Тюремный переулок.  

На 1874 год в Тюремном переулке по нечетной стороне кроме тюремного замка, этапного двора и тюремных огородов было всего два домовладельца – коллежский асессор Степан Рымаренко и купец Алексей Скрынников. По четной стороне домовладельцев было больше: статский советник Стоянов, врач Александр Ковальчуков, крестьянин Матвей Орехов, титулярный советник Семигановский, надворный советник Лев Филонов, мещанин Василий Шмитьков, Борис Филонов и солдат Фёдор Володьков.

Поначалу Тюремный переулок не был загружен транспортным потоком, до 1882 года транспорт шел по Александровской улице, главным образом движение грузов со станции «Харьков» товарный. С открытием конного трамвая (конки), её маршрут проложили к Харьковскому вокзалу по Александровской улице на Привокзальную площадь. И поэтому движение грузов между Конторской и Коцарской улицами пошло по Тюремному переулку, при этом нагрузка была такой интенсивной, что он постоянно был в рытвинах и ямах.

Между 1886 и 1889 годами Тюремный переулок был переименован в улицу. По нечетной стороне шли: 3-я полицейская и пожарная часть, тюремный замок, тюремная больница, дворы купца Серикова, почетного гражданина Одинцова, купца Михайлова, мещанина Мурзина. По четной: дворы Акционерного общества «Новая Бавария», вдовы Стояновой, Александровская больница, княгини Шаховской, рижского гражданина Блумфельда, наследников Ковальчуковых, поручика Матушинского, мещанки Скоробогатовой, наследников Хмары, мещанина Лашина, крестьянина Щербатенко, дворянина Филонова, мещанина Балясникова.

В 1889 году на углу Коцарской и Тюремной была открыта дешевая харчевня, где обед для бедных стоил 4-5 копеек, но, как водится, здесь сразу начались скандалы, ругательства и драки.

В 1890-е годы по Тюремной улице и далее по Коцарской проезжали от складов железной дороги к Первому городскому угольному складу на Пискуновской леваде ломовые «ваньки» с колымагами нагруженными крупными кусками антрацита, тут то их и встречали «застрельщики» забалтывая, а в это время «угольщики» сбрасывали крупные куски угля на дорогу, подбирали и разносили в ближайшие дворы. Собрав партию угля сбывали его в мелкие лавки и заведения по низким ценам.

В 1890-е годы Николай фон Дитмар построил на Тюремной улице № 10 металлический завод, который производил трубы, насосы, буровой инструмент, плуги, производил бурение и устройство водопровода.

Тюремная улица была переименована 20 сентября 1936 года в честь партийного деятеля Афанасия Петровича Любченко, но ненадолго, с 27 сентября 1937 года она получила имя Оружейной. В годы оккупации 1941-1943 годов ей возвращалось старое имя Тюремная. Настоящее имя Маршала Малиновского она получила 14 февраля 1968 года в память о министре обороны СССР маршале Советского Союза Родионе Яковлевиче Малиновском, умершем в 1967 году.