1960年，用米格-21改装的发动机试飞验证机E-150，对米格-25的动力装置R-15-300加力式涡喷发动机开始试飞。次年4月第二架验证机E-152上天。随后装生产型发动机R-15B-300的第3架验证机E-152M试飞。
1961年3月10日，米高扬签署研制米格-25原型机E-155的指令。1962年侦察机全尺寸样机审定委员会开审定会。1963年12月米格-25的第一架原型机（侦察型）E-155R-1出厂，1964年3月6日，苏联著名试飞员费多托夫首次驾机升空。同年9月9日第二架原型机（截击型）E-155P-1开始试飞。随后第三架原型机（侦察型）E-155R-3也参加试飞。三架原型机各装两台R-15B-300发动机，并在1965~1977年间，以E-266代号创造过8项飞行速度，9项飞行高度和6项爬升时间的世界纪录。
米格的第一种超音速战斗机米格-19在零摄氏度的空气中以马赫1.3飞行时，机首与气流摩擦生热，温度达到72摄氏度。而在以马赫2.05飞行的米格-21上，这一温度上升到107摄氏度。估算得出马赫3时，这一温度将达到300度。这使得在机体结构要采用耐热而不能太重的金属材料，这个问题还算好解决，因为当时苏联的金属应用技术已相当完善。但当时苏联却没有一种半导体能够在65摄氏度以上的温度里工作。因此想飞3倍音速，必须解决这一问题。
经米格设计局与有关科研部门及厂家合作，研制米格-25的前期可行性准备得以完成。在动力系统方面，苏联当时航空发动机的顶尖人物米库林和图曼斯基为米格-25研制了大推力的R-15B-300涡喷发动机。因此米格-25研制的主要问题就集中在机体设计和电子火控系统/飞行控制系统问题。
苏联中央空气动力研究院为此进行了大量风洞试验，最后选中双发双垂尾两侧进气上单翼布局，有双腹鳍，整机有很多劈尖线条，完全是一种高速风格。这是米格第一种两侧进气设计，也是第一种双垂尾设计。在机体材料方面，传统的飞机结构材料硬铝因为耐热能力差而不能使用。钛金属耐热能力和重量方面都符合要求，但是昂贵，难加工，且苏联缺少耐高温的铆钉等连结材料。经反复考虑后米高扬决定用钢，在某些关键部位用钛铝合金。这是因为钢虽然笨重，但在耐高温方面能符合要求，且焊接技术成熟，能避开高温铆钉这一问题。
