1958 年 6 月 4 日，部长会议发批文，指令研制截击机-雷达-导弹系统，要求挂载两枚雷达半主动制导 K-9（后定名为 R-38，北约代号 AA-4“锥子”）空空导弹，具有空地自动数据链。1959 年春开始设计，1960 年 2 月期间，原型正在组装，意外地突然接到命令，中止一切工作，所有设计资料和工装全部销毁。
这是一个特殊的时代。洲际导弹的试验成功似乎为未来战争的方向指出了一条新路，导弹制胜论甚嚣尘上，传统空军的价值受到严重怀疑，各国的研制项目纷纷下马，苏联也不例外，T-37 只是其中的一个。米亚希斯切夫和拉沃奇金的设计局被解散，后米亚西斯切夫设计局恢复，但拉沃奇金在恢复的时候转行到火箭去了，成为今日拉度卡设计局的前身。
1960 年开始，苏联防空军对截击机的作用重新思考。苏-9、苏-11 的低空性能成为显眼的缺陷，Orel 雷达的下视性能更加成问题。改进的 Orel-2 雷达天线太大，装不进苏-11，于是提出新型截击机的要求。苏霍伊有备而来，理所应当地承担了设计任务，早早就获得了生产型代号。
新机的设计局代号为 T-58。为了尽量降低技术风险，最大可能地利用现有生产线，T-58 采用苏-11 的机翼、尾翼和后机身，发动机计划采用 AL7F-2。前机身全新设计，采用锥形机头，两侧进气道。和 P-1 不同的是，两侧进气口为矩形截面，采用斜板调节，而不是 P-1 的半圆形进气口和半锥调节。矩形进气口和斜板调节可以在低速时全开，没有进气损失。半锥即使再最靠前的“全开”位置也依然对进气有所损失。
T-58 在座舱部和机身中断收腰身，以满足面积律的要求
苏-15 是第一架两侧矩形进气口的苏霍伊战斗机
1961 年初，设计完毕，开始制造原型机，一架用于地面静态试验，一架用于试飞。但原型机尚在制造中，防空军就改了主意，提高性能和可靠性的要求，这样，单发的 T-58 就不能达到要求了。苏霍伊也只好中途易帜，改用双发，编号改为T-58D。
双发的 T-5 加宽的后机身带来阻力增加，但双发的强劲无可置疑。T-5 的双发经验对后来 T-58 很有用
苏霍伊对双发并不陌生，T-5 就是采用双发的 T-3。防空军的中途改主意给了苏霍伊一个从头开始的机会，苏霍伊索性采用面积律，在机头雷达罩后座舱处收腰，使座舱盖引起的截面积增加得到补偿而保持截面积均匀变化。在中机身段，苏霍伊还做了一个更鲜艳的“蜂腰”，以满足面积律的要求，减少跨音速阻力。
T-58D 不仅采用双发，还要求采用新的有 Orel-2 雷达，天线直径达到 920 毫米，挂载两枚 K-40 空空导弹。R21 发动机后来下马，T-58D 改用图曼斯基 R11 发动机，和米格-21 共用，军用推力 3,900 公斤，加力推力 6,200 公斤。
1962 年 2 月 5 日，部长会议的正式批文下达，包括 T-58D 和雷达、导弹系统的整个截击系统进入全面研制。为了加快设计进程，T-58D 继续采用苏-11 的机翼、尾翼和起落架，机身为全新设计，更重要的是全新的全自动火控-飞控系统，可以完成全程自动截击。第一架原型主要试验速度、升限、加速度、航程、油耗，所有测试都分带外挂和不带外挂进行。
1962 年 5 月 20 日，伊柳辛驾驶原型机首飞。飞行性能大体达到设计要求。但试飞还在进行中，防空军要求改换更先进的由米格-25 的 Smerch 雷达改进而来的 Taifun 雷达，于是苏霍伊重新设计机头锥，比原先进一步拉长，座舱盖也重新设计。为了改善方向安定性，差点像米格-23 一样，在机腹安装可折叠的腹鳍，最后还是没有，加大垂尾达到同样的目的。垂尾和腹鳍同样可以大大提高方向安定性的目的，但腹鳍在大迎角时也能发挥作用，垂尾要达到同样的效果，需要大大加高，重量代价较大。但腹鳍的问题是影响机身下的净空，太小的腹鳍没有用，太大的腹鳍影响起飞拉起，容易刮地。可折叠的腹鳍避免了这个问题，但增加了结构的复杂性和重量。T-58D 不以高机动的空战格斗为重点，所以适当加大垂尾就可以满足一般的方向安定性要求。说到底，这都是设计时综合妥协的结果，没有哪一个方案是绝对优于另一个方案的。
再次试飞时，Taifun 雷达还没有就绪，依然用 Orel-2 雷达装在试飞飞机上，起落架的刹车加装酒精-水冷却系统。水冷却的效率高，也便宜，但冬天要结冰。加了酒精后，就可以大大降低冰点。
二号机一直在等雷达，直到 1963 年 5 月 4 日才由伊柳辛首飞。二号机具有全套目标航电，包括全新的 Orel-2 雷达。10 月开始导弹发射试验和作战试验，1964 年 6 月才结束。伊柳辛、拉沃兰迪耶夫、佩特林、彼得洛夫和国家鉴定试飞委员会主席、防空军司令萨维茨基参加试验，试验出乎意料地顺利，防空军对试验结果很满意，1964 年 6 月 16 日决定按苏-15 的编号投产，但要求增加航程和改善方向安定性及操控性。
苏霍伊把中机身段的蜂腰取消，从进气口到尾喷口把机身侧面拉直，增加机内油箱容积。操纵面的作动角度加大，进气道调节斜板的反应时间缩短，以改善操控性。但更大的问题在于找一个飞机工厂投产苏-15。
苏-11 的操控性不好，雷达和导弹的性能也不能使防空军完全满意，所以苏-11 在新西伯利亚只生产了区区 112 架就早早中止，工厂转产雅克-28 截击机。苏联的飞机设计局和飞机工厂之间没有固定的协作关系，设计定型后，生产有一个先来后到，哪个工厂有剩余产能就在哪里投产，要是谁也没有剩余产能，就可能面临无疾而终的危险。苏-6 在二战中就因为要挤占已经投产的伊尔-2 不成而夭折，苏霍伊当然对此记忆犹新。为了确保设计局的前程，苏霍伊和雅科夫列夫狠斗了一番，除了航程外，苏-15 的性能全面优于雅克-28，最后决定雅克-28 为苏-15 让路。1966 年 3 月 6 日，第一架生产型苏-15 下线，工厂试飞员索罗金驾机首飞。6 月二号机首飞，1967 年，苏-15 开始批量交付防空军，生产一直持续到 1979 年。1967 年 7 月 9 日，新生的苏-15 和米格-23、米格-25 一起，参加多莫达多沃航空表演，纪念十月革命 50 周年。苏-15 作为防空军的主力，一直服役到到 90 年代中期。至此，苏霍伊在苏联战术飞机世界的半壁江山得以建立。