После Кавказской войны Черноморское побережье Кавказа нуждалось в дорожном сообщении, регион не мог динамично развиваться без постоянного сообщения. Трудности были до появления Новороссийско-Сухумского шоссе, начатого в 1891 году. Нередко дорогу именовали Голодным шоссе. Руководителем строительства стал Анненков Михаил Николаевич (1835-1899), именем которого также иногда называли дорогу.
Родился Михаил Николаевич 30 апреля 1835 г., воспитание получил в Пажеском корпусе, откуда вышел в 1853 г. и поступил на службу в конные пионеры. В 1857 г. поступил в Академию Генерального штаба, где блестяще окончил курс. В 1863 году отправился в Польшу, где принимал участие в усмирении мятежа, а потом в разных комиссиях по преобразованию края. Был произведен в полковники. В 1867 г. он поместил ряд статей в «Военном сборнике» по вопросу «о применении железных дорог к военному делу». Статьи очень заинтересовали общество. В 1869 г. Анненков был произведен в генерал-майоры и назначен заведующим передвижением войск по всем железным дорогам России.
На участках Новороссийско-Сухумского шоссе от Новороссийска до Туапсе, протяжением 192 версты, и от Сочи до Нового Афона, протяжением 150 верст, разработка полотна дороги и шоссирование его окончены в 1896 году. С тех пор главную работу составляла постройка больших железных мостов через реки, где первоначально оставлены были броды и частью где построены были деревянные мосты, которые, вследствие быстро наступавших паводков и громадных скоростей течения горных рек Черноморского побережья, подвергались частым разрывам, почему не могли обеспечивать непрерывности сообщения по шоссе, а в связи с весьма коротким сроком службы деревянных конструкций, на побережье имели значение лишь временных сооружений. Постоянные мосты построены железные на каменных, глубоко заложенных опорах со струенаправляющими дамбами; с целью избежать промежуточных опор, опасных на горных реках как во время устройства их, так и при дальнейшем их существовании, мосты эти до отверстия в 50 сажень включительно построены однопролетными. Большие железные мосты построены через реки: Адербу Жанэ, Догуаб, Пшаду, Вулан, Джубгу, Казачью, Небуг, Агой, Паук, Мацесту, Хосту, Кудепсту, Хероту, Мзымту, Гагринский сухой овраг, Жоэквару, Бзыбь и еще на нескольких реках Абхазии.
Для южного края России строительство дороги имело такое же важное значение, как строительство Транссибирской магистрали в азиатской части империи.
На всеимперской стройке работал в качестве обычного рабочего молодой М.Горький.
