Казна выделяла на развитие прогрессивного вида транспорта немалые деньги. И все же их недоставало. Прежде всего из-за распыления сил на многих направлениях. Поэтому были созданы все условия для образования акционерных обществ, которые могли строить и эксплуатировать новые железные дороги. Общества стали появляться одно за другим. И почти везде большую роль играл иностранный капитал, использующий льготы, предоставленные государством, для извлечения максимальной прибыли.
Вскоре с предложением построить дорогу от Москвы на Харьков и Одессу и от Харькова на Феодосию выступил американец А. Шифнер. Его условия признали невыгодными.
В 1854 году в спешном порядке организовали особую экспедицию для изыскания возможностей строительства новых железных дорог по направлениям Москва — Харьков — Феодосия (с веткой на Севастополь и линиями на Донбасс и Ростов-на-Дону) и Харьков — Одесса под руководством строителя первой отечественной магистрали П. Мельникова. В экспедицию входило семь изыскательских партий во главе с инженерами, отличившимися на сооружении магистрали Санкт-Петербург — Москва, Д. Журавским, В. Сеничевым, В. Папаевым и другими. За два с половиной года экспедиция протрассировала около 4 тысяч верст, и в начале 1857 года П. Мельников представил предварительный проект строительства железных дорог к югу от Москвы.
И уже весной образовалась компания учредителей при участии торгового дома «Томсон Бенар и Ко» и многих высокопоставленных лиц (всего 228), которая предложила создать акционерное общество для строительства железной дороги от Одессы через Балту, Брацлав, Киев, Нежин и Кролевец до встречи с предложенными к сооружению Феодосийской и Либавской дорогами. Но новое общество не получило концессии. В то время предполагалось, что с учреждением Главного общества российских железных дорог (26 января 1857 года) концессия на строительство южной линии от Москвы до Феодосии будет выдана ему. Однако общество оказалось несостоятельным из-за других строек и в ноябре 1861 года было освобождено от сооружения этой магистрали.
В 1858 году по поручению группы лондонских банкиров англичанин Топпе внес предложение о постройке дороги между Москвой и Феодосией. Правительство, придавая большое значение этой дороге, пошло на чрезвычайно большие льготы иностранной компании: предоставляло ей право эксплуатировать дорогу в течение 99 лет, определило стоимость версты в 97 251 рубль, давало гарантию дивидендов 5 процентов. Кроме того, компания получала право привлечь для работы войска, беспошлинно ввозить из-за границы материалы, подвижной состав и другие льготы. Но, несмотря на все условия, учредители компании не смогли организовать дело, и 12 января 1861 года концессия была объявлена несостоявшейся.
Наступил трудный период для железнодорожного строительства. Новые общества не образовывались. А между тем существовала острая необходимость в целой сети железных дорог. В проекте 1862 года южная линия Москва — Курск — Харьков — Крым (протяженностью в 1440 верст) занимала первое место в перечне «самонужнейших дорог».
В 1863 году П. Мельников назначается Главноуправляющим путями сообщения и публичными зданиями. Он продолжает проводить в жизнь идею сооружения Южной дороги за счет казны, считая, что это обойдется намного дешевле. С его точки зрения, это дало бы возможность еще и рассеять господствовавшее за границей предубеждение относительно невыгодности помещения иностранных капиталов в строительство железных дорог.
Тем временем в борьбу за строительство Южной дороги активно включилась и харьковская общественность. В конце концов этот вопрос был вновь вынесен на рассмотрение царя.
3 апреля 1865 года представитель общественности Харькова Н. Кукольников обратился с письмом к харьковскому губернатору. А 4 мая того же года губернатор А. Сиверс направляет письмо харьковскому городскому голове, в котором говорится: «Препровождается письмо Н. Кукольникова о предположительном проведении железной дороги от Орла через Харьков до Таганрога и Ростова и о пожертвовании городской земли как для устройства станции с принадлежащими постами, так и для проведения самой дороги. Поручаю Вам, собрав харьковское городское общество, предложить на обсуждение настоящее обстоятельство и составленный об этом приговор предоставить на мое рассмотрение. При этом надеюсь, что городское общество оценит всю выгодность настоящего долга и примет его с сочувствием».
В ответ на письмо состоялось собрание городского общества и 19 мая 1865 года А. Сиверсу и городской думе было направлено решение, в котором говорилось, что и со стороны общества не встретится ни малейшего препятствия на передачу безвозмездно под железную дорогу того количества земли, которое будет признано нужным.