Максим Ноготков основал свою компанию в 1995 г. Тогда она называлась «Максус» и торговала электроникой: «В какой-то момент мы занимали до 40% рынка страны по аудиоплейерам и радиотелефонам. Тогда у нас было около 30 магазинов». В 2000 г. «Максус» занялся оптовыми поставками мобильных телефонов, а в 2001 г. переключился на розничный бизнес. На разработку проекта у команды Ноготкова ушло девять месяцев. В апреле 2002 г. под брендом «Связной» открылся 81 магазин. Ноготков утверждает, что на тогдашнего лидера сотовой розницы — «Евросеть» Евгения Чичваркина — не ориентировался: «Мы просто делали свой проект. Женя приехал ко мне в офис познакомиться в конце 2001-го — начале 2002 г.». Ноготков считает Чичваркина талантливым бизнесменом: «Конкурировать с ним было интересно. Он очень харизматичный человек».
Осенью прошлого года Чичваркин и его партнер Тимур Артемьев продали «Евросеть», а в январе 2009 г. основатель «Евросети», уехавший к тому времени в Лондон, был заочно арестован по уголовному делу о похищении человека (по версии следствия, Чичваркин в 2003 г. распорядился насильно удерживать экспедитора «Евросети», которого подозревал в хищении телефонов, до тех пор пока тот не возместит ущерб). «Мне кажется, я хорошо понимаю способ мышления и принятия решений Евгением, поэтому я считаю, что судом принято неправильное решение, — сожалеет Ноготков. — Степень общественной опасности Евгения Чичваркина, мягко говоря, переоценена».