Еще до того времени, когда Одесско-Балтская дорога была закончена постройкой, неугомонный П. Е. Коцебу задумал изменить ее первоначальное направление. Вместо Киева он предложил тянуть рельсы на Кременчуг и далее на Харьков; другую линию вести к австрийской границе до Новоселиц. Уязвимым местом его плана было то, что Киев оказывался вне связи с крупнейшим черноморским портом России. Помимо этого, соединение Одессы с обеими столицами отодвигалось на неопределенное время. Предложение Коцебу наделало много шума. Оно обсуждалось и в прессе, и в ученом мире, и в правительственных кругах.
2 и 7 декабря 1864 года состоялось специальное заседание статистического отдела Русского географического общества, где скрестили копья сторонники киевского и кременчугского направлений. Киевскую партию возглавляли M. H. Катков и И. С. Аксаков (не явившиеся на заседание); противную — П. Е. Коцебу и директор статистического отдела Министерства внутренних дел П. П. Семенов.
Приверженцы киевского направления оперировали геополитическими и стратегическими аргументами. Лишь В. П. Безобразов — известный экономист либерального направления — доказывал, что дорога через Киев облегчит сбыт на южной Украине изделий московских текстильных фабрик.
Одесский банкир Рафалович прочел доклад на французском языке. Он указал на исключительную важность кременчугского направления для расширения российского экспорта через Одессу. Ни в Подольской, ни в Киевской губерниях производство товарной пшеницы не могло быть увеличено, тогда как посевные площади Харьковской и Екатеринославской губерний постоянно росли. Далее трехсотверстного расстояния вывоз хлеба он вообще считал нецелесообразным ввиду высокой стоимости провоза.
Большинство участников дискуссии высказались в пользу киевского направления. Но император решил иначе: 28 декабря 1864 года состоялось высочайшее повеление, которым предложение П. Е. Коцебу о направлении дороги от Балты на Харьков получило силу закона. 28 марта 1865 года были утверждены и основные условия контракта. Его удостоился проверенный в деле контрагент казны — барон К. К. Унгерн-Штернберг. Для производства строительных работ в его распоряжение назначались две бригады штрафных солдат общей численностью 9 тыс. человек.
Дорога должна была иметь протяженность 234 версты, сметная стоимость ее составляла 45 тыс. руб. на версту, а всего 10,5 млн. Предварительные изыскания были сделаны подрядчиком, он же выбрал и основное направление пути. Условиями контракта допускалось и отклонение от избранного направления, но не свыше 5 верст в сторону. За строительством наблюдал инспектор от Министерства путей сообщения; в министерство представлялись и все технические отчеты по работам. Подрядчик обязался не только построить магистраль со всей положенной инфраструктурой, но еще и снабдить ее подвижным составом. Он должен был поставить 9 паровозов весом до 28 т, 25 — до 35 т; вагонов пассажирских — 90, товарных — 560.
