Проект поддержал член ЦК КПСС Леонид Ильич Брежнев, который спустя пять лет станет главой государства. В августе 1963 года Совет министров СССР издал постановление об учреждении математических школ-интернатов, и в декабре они открылись в Москве, Киеве, Ленинграде и Новосибирске. Большинством их руководили ученики Колмогорова, который лично наблюдал за составлением учебных планов.
В августе Колмогоров организовал в подмосковном поселке Красновидово летнюю математическую школу. Были отобраны 46 победителей и призеров Всероссийской математической олимпиады. Колмогоров и его аспиранты вели занятия, читали лекции по математике и водили учеников в походы по окрестным лесам. Наконец, 19 юношей были отобраны для учебы в новой физико-математической школе-интернате при МГУ.
Они оказались в новом, странном мире. Колмогоров, который сорок лет вынашивал проект новой школы, разработал не только методику индивидуального обучения, основанную на дальтон-плане, но и полностью новую школьную программу. Лекции по математике, которые читал в том числе сам Колмогоров, имели целью ввести детей в мир большой науки. Принимались в расчет способности учеников: Колмогоров охотнее выбирал детей, в которых обнаруживал присутствие "божьей искры", чем тех, кто досконально знал школьный курс математики. В колмогоровской школе — возможно, единственной в СССР — преподавали вузовский курс истории древнего мира. Учебная программа включала большее количество уроков физического воспитания, чем их было в обычных школах. Наконец, Колмогоров лично просвещал учащихся, рассказывая о музыке, изобразительном искусстве и древнерусской архитектуре, и устраивал походы — пешие, лыжные или лодочные.
"В интернате <...> нас призывали интересоваться не только математикой и физикой, но и развиваться всесторонне. Походы и стихи нам нравились, — вспоминает один из учеников Колмогорова. — Музыку понимали немногие — она требует подготовки. Но требования интереса к "общественным наукам" нас смешили и раздражали. Хорошо, что сам Андрей Николаевич по этому поводу отмалчивался". Таким образом, Колмогоров не только стремился передать ученикам гуманистические ценности, как он их понимал, но и оберегал детей от марксистской идеологии, под воздействием которой они находились в средней школе и которую им будут упорно навязывать (и которую им вновь придется терпеть) в вузе.
Колмогоров стремился не только создать обойму элитарных математических школ. Он хотел обучить настоящей математике всех детей, которые могут учиться. Он подготовил проект модернизации учебной программы с тем, чтобы школьники учились не сложению и вычитанию, а математическому мышлению. Он курировал реформу, которая ввела в учебные планы изучение простых алгебраических уравнений с переменными и использование в обучении компьютеров — чем раньше, тем лучше. Кроме того, Колмогоров стремился преобразовать школьный курс геометрии, чтобы открыть дорогу неевклидовой геометрии.