Создание нового самолета потребовало включения в работу целого ряда организаций. Кроме традиционных участников, таких, как двигателестроительное ОКБ С. Туманского, ЦАГИ, фирмы, создающие оборудование и вооружение, к процессу проектирования подключили Всесоюзный институт авиационного материаловедения (ВИАМ), в задачу которого входили поиск и разработка новых материалов. При длительных полетах на большой сверхзвуковой скорости ряд элементов конструкции должен был нагреваться до 200-300°С. Необходимо было найти марки сплавов из стали и титана, не терявших прочностные качества при такой температуре и позволявших построить самолет с заданной массой. Потребовалась разработка и новых лакокрасочных материалов, стекла, герметики и резины.
Традиционно строивший МиГи Горьковский авиационный завод также начал подготовку к производству машины. Нужно было освоить новые технологические процессы обработки жаропрочных металлических сплавов, неметаллических соединений, автоматизировать сварку и термообработку крупногабаритных отсеков и агрегатов. Советская авиационная промышленность готовилась преодолеть свой барьер в создании самого скоростного самолета третьего поколения.
Первую опытную машину Е-155Р-1 перевезли из цеха машиностроительного завода «Зенит» (так в прежние годы называлось ОКБ А. Микояна и его производство) на аэродром летно-испытательной станции в Жуковском в декабре 1963 г. На постройку прототипа ушел год. Первый экземпляр самолета представлял собой вариант разведчика без разведывательного оборудования (вместо него для центровки в носовой части установили груз).
Е-155Р-1 – первый прототип МиГ-25
На законцовках крыла крепились два металлических топливных бака общей емкостью 1200 л. Одновременно они выполняли роль противофлаттерных грузов. К задней нижней части крыльевых баков крепились вертикальные плоскости трапециевидной формы, отклоненные на небольшой угол во внешние стороны. Они увеличивали путевую устойчивость и одновременно уменьшали поперечную, то есть давали эффект обратного крыла (установленное на первом и втором прототипах крыло не имело поперечного V. В передней части воздухозаборника Е-155Р-1, как и на последующих прототипах самолета, были предусмотрены узлы для установки переднего горизонтального оперения, которое предназначалось для улучшения балансировки на больших скоростях. К моменту установки на самолет тягу каждого двигателя на форсаже удалось довести до 11200 кгс.
Прототип был окрашен в светло-серый цвет, а передняя часть фюзеляжа – в черный. Черной противоореольной краской покрыли всю поверхность самолета вплоть до фонаря кабины пилота. Необычный четырехзначный номер, выполненный большими цифрами красного цвета, украшал фюзеляж машины перед воздухозаборниками. Число «1155», нанесенное на борту, обозначало порядковый номер прототипа и его шифр (первый самолет изделия Е-155).
Александр Федотов, назначенный шеф-пилотом фирмы после аварии Георгия Мосолова на самолете Е-8, поднял Е-155Р-1 в воздух 6 марта 1964 г. С этого момента начались заводские испытания машины. Второй опытный экземпляр был направлен для статических исследований. На третьем экземпляре, также построенном в варианте разведчика, летчики А. Федотов, П. Остапенко, Б. Орлов, О. Тучков, А. Кравцов, А. Бежевец, И. Лесников и другие выполнили основной цикл испытаний.
Третий прототип Е-155Р-3 (практически параллельно с ним – первый перехватчик Е-155П-1) строили с учетом информации, полученной на начальном этапе испытаний Е-155Р-1. Машина значительно отличалась по конструкции. С законцовок крыла сняли топливные баки с дополнительными плоскостями и вместо них в небольших цилиндрических обтекателях установили противофлатгерные грузы (иногда их называют балансировочными штангами). Крыло установили с отрицательным углом поперечного V, равным -5е . Изменили конструкцию вертикального оперения. Кили увеличили по высоте, но их законцовки имели не прямой, а косой срез (соответственно изменилось и местоположение антенн оборудования в радиопрозрачных частях этих законцовок). Эти изменения повысили путевую устойчивость. Носовую часть фюзеляжа приспособили для размещения разведывательной аппаратуры, которую установили в процессе испытаний. На третьем прототипе под фюзеляжем установили подвесной бак большого размера, длина которого превышала половину длины самолета. Его емкость составляла 5300 л. Такой огромный подвесной резервуар с топливом в практике советского самолетостроения применялся впервые.