Однак, звідки точно вони прийшли ніхто не знає і тільки легенди кажуть, що «вони прийшли з глибини рівнин, що між скелями».
Очолював групу бродячих Тольтеків-Чичимеків вождь Мішкоатль, чиє ім'я в перекладі означало Хмарний змій або Чумацький Шлях. Під його керівництвом тольтеки покинули Чікомосток (міфічну відправну точку) і попрямували в Чолулу. Поки вони йшли в Чолулу, Мішкоатль підкорив Кулуакан і одружився з знатною жінкою Чімаман (можливо вона була дочкою правителя Кулуакана). Таким чином, відбувалася асиміляція прийшлих народів з цивілізаціями, які вже були до їх приходу (і не тільки тольтеки так чинили). Згідно з кодексом Чимальпопока, Мішкоатль підкорив Теотіукан і прилеглі до нього території і зробив Кулуакан першою столицею тольтеків.
Від союзу Мішкоатля і Чімаман народився Се Акатль (Один Тростник), Топільцин (Принц), Кецалькоатль (Пернатий Змій). Але Кетцалькоатль не побачив свого батька - він був убитий соратниками.
Своє дитинство Кетцалькоатль провів у місті Тепостлан неподалік від великого культурного і ритуального центру Шочикалько. Ставши дорослим, він на прохання і за допомогою вірних його батькові знати, шляхом запеклої політичної боротьби отримує владу в Кулуакані. Далі він у 980 році переносить столицю тольтеків з Кулуакана - спочатку ненадовго в Тулансінго, а потім вже в Тулу Шикокотітлан, або Толлан (сучасний штат Ідальго). Тула стає центром світу тольтеків і об'єднує в єдину конфедерацію кілька племен і найстаріших міст (Куаучінанко, Куаунауак, Куаупан, Уастенек).
Місто швидко розвивається і стає найкрасивішим, найбагатшим і технічно досконалим в долині Мехіко, згодом про його багатство залишилися легенди ацтеків. У новій столиці виникає військово-релігійне мистецтво, зразком якого виступив храм Тлауіскальпантекутлі («Владики світанку»), що зберігся до наших днів, Венери. До храму вела платформа з трьома довгими рядами суворих колон, що з'єднувалися різними перекриттями, між якими в особливому поглибленні горів вічний вогонь.
Ставши правителем тольтеків, Кетцалькоатль починає низку реформ: політичних - з метою посилення концентрації влади в своїх руках і релігійних, в яких він забороняє приносити в жертву людей і дозволяє жертвувати богу Кетцалькоатлю метеликів, змій і птахів. Одночасно він намагається зробити бога Кетцалькоатля богом номер один (а то навіть і єдиним) тольтекського пантеону.
Однак, його реформи не припали до душі жерцям багатьох богів і насамперед жерцям культу Тецкатліпокі («Дзеркало, що димиться»). Найбільш кровожерливого і постійно вимагає людської крові у вигляді жертвопринесень. Послідовники Тецкатліпокі організували дискредитацію Кецалькоатля в очах народу, намагаючись різними способами змістити його з посади правителя тольтеків. Їм це вдається, і в 987 році Топільцин був вигнаний з Тули.
У 987 році н.е. ватажок тольтеків Се Акатль Топільцін Кетцалькоатль (або, по-майяски, Кукулькан) з'являється в майяському місті Чічен-Іца на півострові Юкатан і займає його. Прихід вождя тольтеків не був мирною подією: у написах з Чічена йдеться про вторгнення загарбників, які повалили династію майя. З малюнків і написів у Храмі воїнів можна дізнатися, що тольтеки спочатку виграли морську битву проти майя, а потім перемогли їх у битві на суші в якомусь місті (можливо, саме в Чічені).
Здобувши перемогу, тольтеки попрацювали своїх супротивників, а їх лідерів принесли в жертву богу Сонця. Тольтеки дали Чічен-Іці друге життя і, як мінімум століття, чиченицькі тольтеки підтримували зв'язок з тольтеками з Тули. Влаштувавшись у Чічен-Іці, тольтеки і союзні з ними племена незабаром поширили свій вплив на більшу частину півострова Юкатан. Але на початку XIII століття - силами трьох міст (Іцмаля, Майяпана і Ушмаля) у вирішальній битві війська Чічен-Іци були розгромлені. Ера тольтеків на півострові Юкатан закінчилася
Після вигнання Кетцалькоатля з Тули, влада переходить в руки Матлакшочітля, а потім до Науйоцина, Матлакоацина, і т. д. Всього тольтекська династія налічує десять правителів. Останнім правителем тольтеків був Уемак. Він правив близько 76 років. У його правління сталося безліч бід, у тому числі і сім голодних років. У 1156 або 1168 році літній Уемак переносить столицю в Чапультепек (нині парк на заході Мехіко) і здійснює ритуальне самогубство.
Столиця Толлан - продовжувала процвітати, поки до 1200 року (коли тольтеки не змогли протистояти черговому вторгненню чичимеків) не була знищена і спалена дотла новою хвилею диких чичимеків, які прийшли з півночі. Після цього в долині Мехіко склалося наступне співвідношення сил: у Кулуакані проживали тольтеки-колуа, в інших містах - представники племен, які мігрували пізніше.
