Концессию на возведение дороги Поляков получил 1 марта 1868 года. И тут же возникла первая проблема: как выкупить земли у землевладельцев. Самуил Соломонович решил ее довольно быстро, хотя некоторым из владельцев пришлось заплатить за землю в полтора-два раза больше ее «красной» цены.
Второй важный вопрос, который необходимо было решить Полякову, был связан с определенными обязательствами концессионера, предусмотренными контрактом: он должен был заложить угольные копи и построить металлургический завод.
Поляков подошел к этому вопросу основательно: организовал общество по разработке каменноугольных копей и нанял английских инженеров. Уголь, необходимый для его железных дорог, скупался им же организованным обществом у мелких шахтовладельцев. Они вынуждены были продавать Полякову уголь практически за бесценок в надежде выручить хоть какие-то деньги, поскольку сами вывезти его в другие районы не могли. Поляков давал вагоны и предоставлял льготные тарифы только своему обществу.
Строительные работы начались в мае 1868 года. Вот как описывали их «Харьковские губернские ведомости» в июньском номере:
«Успешность производства этих работ в течение мая превзошла все ожидания строителей, этому способствовала сухая погода. В июне окончательно была установлена телеграфная линия. К месту, где предположено построить Харьковскую железнодорожную станцию, безостановочно происходит подвоз необходимых материалов».
В феврале 1869 года на станции Харьков «вчерне» были уже построены здания мастерских, паровозных сараев, водоподъемных зданий, «прибыли из-за границы инструменты и оборудование для мастерских, половина поворотных кругов, из числа подвижного состава доставлено 9 паровозов, 7 пассажирских, 550 товарных вагонов; к открытию движения начали доставляться каменный уголь, антрацит, дрова…». Двадцать второго мая в Харьков прибыл первый поезд, в котором приехала «приглашенная строителем дороги публика» и представители власти – курский и харьковский губернаторы. Уже упомянутые ранее «Харьковские губернские ведомости» освещали прибытие поезда:
«…состав приветствовали восторженными криками многочисленные толпы народа, расположившиеся на станции и вблизи нее на протяжении нескольких верст. Преосвященным Германом с духовенством совершено было благодарственное молебствие, и затем строителем дороги был предложен участвовавшим в торжестве завтрак».