1956年赫鲁晓夫任命45岁的戈尔什科夫代替主张建造大型军舰的库兹涅佐夫出任海军总司令。戈尔什科夫费了不少心机，才挽救了13艘“斯维尔德洛夫”级巡洋舰免遭拆毁的命运。
赫鲁晓夫对海军的不重视在整个苏联已不是什么秘密，然而，赫鲁晓夫亲手挑选的海军总司令戈尔什科夫，与赫鲁晓夫本人的看法却并不一致，甚至可以说大相径庭。只不过为了能坐稳海军总司令的座椅，为了苏联国防建设的需要，戈尔什科夫才将自己的观点深埋在心中，在出任海军总司令的前几年中，他表面上支持赫鲁晓夫的意见，甚至在公开场合这样宣称：“航空母舰称霸海洋的时代已经过去了，它必然地将成为历史的陈迹。”“一旦战争爆发，对于拥有先进作战力量的敌人来说，航空母舰无异于漂浮于海洋上的巨型僵尸。”
50年代末60年代初，美国建成了多艘弹道导弹核潜艇，其矛头直接威胁到苏联的内陆腹地。赫鲁晓夫不得不同意戈尔什科夫建造用以对付美国海军战略潜艇的反潜巡洋舰及其他反潜军舰的建议。这一次戈尔什科夫采用了障眼法，他将苏联人建造的第一代可载飞机的军舰称之为反潜巡洋舰，这艘后来被正名为苏联第一代航空母舰的“反潜巡洋舰”就这样被戈尔什科夫巧妙地塞进了苏联海军的军舰建造计划。
苏联海军第一代航空母舰命名为“莫斯科”级，该级舰共建两艘：“莫斯科”号和“列宁格勒”号(后来易名为“圣彼得堡”号)，1963年首舰开工建造，两舰于1967年、1968年先后在黑海尼古拉耶夫船厂建成，加入苏联海军舰队的行列。
由于赫鲁晓夫大权在握，“莫斯科”级航空母舰在限制排水量方面做了硬性要求，从而导致该级航空母舰存在不少缺陷，其稳定性、适航性和抗沉性均较差，甚至在风浪稍大时就无法使用鱼雷发射管。该级舰标准排水量15000吨，满载排水量17500吨，全长189米，宽34米，以两台蒸汽轮机推进，总功率73.5兆瓦，双轴双桨，航速31节。
由于该舰命名为“反潜巡洋舰”，故“莫斯科”级外形奇特，前部类似导弹巡洋舰，像台阶一般的舰桥上布满导弹发射架和各种雷达天线，舰桥中部垂直切下，后部是平坦宽阔的直升机飞行甲板，飞行甲板下面是65米长、24米宽的机库，设两台梯形配置的小型升降机供直升机出入机库。在舰桥后方的烟囱下方还有一个可容纳4架直升机的常规机库，共搭载卡-25“激素”直升机14架。舰上武器为两座57毫米双联炮塔，两座SA-N-3防空导弹双联发射架、2座RBU-6000火箭式深水炸弹发射器和两座五联鱼雷发射器。