Основание компании «Межрегиональный ТранзитТелеком» пришлось на период бурного строительства сотовой связи в России. Развитие сетей сотовой подвижной радиосвязи стандартов NMT-450 и GSM к 1994 году в России привело к необходимости появления единого оператора, который бы взял на себя функцию взаимодействия десятков и сотен компаний, предоставляющих эти услуги связи. Не менее важным на тот момент было и возникновение единых федеральных стандартов, по которым такое взаимодействие могло бы происходить. 31 октября 1994 года была создана компания «Межрегиональный ТранзитТелеком», призванная объединить разрозненные сети многочисленных региональных и столичных операторов подвижной радиосвязи в единое телекоммуникационное пространство, обеспечить глобальное пространство для общения многих тысяч абонентов.

МТТ была создана при живом участии крупнейших игроков телекоммуникационного рынка России того времени. Компании "Ростелеком", МГТС, ПТС, "Санкт-Петербургский междугородный и международный телефон", МСС («Московская Сотовая связь») стояли у истоков начала работы компании МТТ, и продолжали активное сотрудничество на протяжении многих лет. Создание МТТ активно поддержали и регулятор – Минсвязи России. Сразу после создания, в 1994 году, начал прорабатываться вопрос сотрудничества и с операторами связи стандарта AMPS (в 1994 году в этом стандарте работал и «Би-Лайн»), к общей сети принял решение присоединиться МТС. На начальном этапе развития, первоочередной задачей стала разработкой алгоритмов взаимодействия отдельных сотовых сетей в национальных рамках, и интеграция такой сети с подобными зарубежными структурами.