Помимо этого необходим был подрядчик, которому можно было бы доверить казенные деньги. Таким подрядчиком оказался известный генерал-губернатору камергер Ф. Унгерн фон Штернберг. Барон — светский человек, не лишенный таланта организатора, сумел через свои петербургские связи добиться получения от казны кредита, который погашался сдачей объекта по фиксированной цене обратно в казну. Разница была прибылью предпринимателя.
Строительство шло по тем временам довольно быстрыми темпами, и уже 5 декабря 1865 года состоялся пуск первой в Украине дороги Одесса — Балта. Нужно сказать, что возведение первой очереди дороги Одесса — Балта с ответвлением Раздельная — Парканы принесло барону доход в размере 35 тысяч рублей ассигнациями, которые он получил после сдачи дороги в эксплуатацию.
Сразу после сооружения железной дороги Одесса — Балта возникли споры о том, в каком направлении продолжать эту линию. Одни предлагали на Киев, другие — на Харьков.
Середина XIX века принесла с собой значительное развитие южных районов России. Важность и значение Донецкого бассейна, высокие темпы роста сельского хозяйства в Украине, развивающиеся индустриальные районы восточной ее части показали, что для дальнейшего подъема экономики края необходимо решить вопрос о перевозках грузов, так как сухопутные дороги уже не справлялись с этой задачей.
Губернский город Харьков находился в 1374 верстах от Санкт-Петербурга и в 697 от Москвы. Проживало в нем постоянно более пятидесяти тысяч жителей. Сам по себе Харьков как будто не располагал преимуществами, которые должны были бы сделать его одним из транспортных центров России. Он не стоял на судоходной реке, не обладал выгодами местности, богатой полезными ископаемыми и способствующими развитию той или иной отрасли промышленности. Но этот город занимал одно из первых мест в России по числу ярмарок и стал своеобразным гостиным двором, складом товаров, перевалочным пунктом между севером и югом страны.
В Харькове проводилось четыре ярмарки в год. Первое место по праву принадлежало Крещенской, которая устраивалась с 6 января по 1 февраля и по обороту уступала в стране лишь Нижегородской и Ирбитской. Хороший зимний путь давал возможность доставлять большое количество товаров с севера. Продавалось их на ярмарке на 20–30 миллионов рублей серебром. При этом многие купцы шли на это, даже если подвоз обходился очень дорого. Если товар не удавалось продать в Харькове, он, как правило, следовал в другие украинские города и в конце концов находил покупателей.