解放乌克兰的任务完成后，解放克里米亚的任务提上了日程。在指挥这个战役过程中，华西列夫斯基仍然担任总参谋长，同时协调乌克兰第三方面军和第四方面军的行动。
苏军统帅部大本营的每一位代表，通常掌管两三个方面军。这种通过直接置身于作战地区的大本营代表指挥部队的形式，证明是行之有效的。
在苏联的整个卫国战争中，争夺克里米亚的战斗一直很激烈。德军竭尽全力死守克里米亚，是因为德军只要守住克里米亚，他们就可以使整个河海沿岸处于其经常的威胁之下，并对罗马尼亚、保加利亚和土耳其的政策施加压力。
此外，克里米亚也是德军进犯苏联高加索地区和稳定整个战场南翼的基地。
根据苏军大本营定下的计划，克里米亚战役的意图在于：
乌克兰第四方面军从北面，即从彼列科普和西瓦什湖；独立濒海集团军从东面，即从刻赤地域，在黑海舰队和游击队的配合下，向辛菲罗波尔—塞瓦斯托波尔这个共同方向同时实施突击，分割敌军，防止其由克里米亚撤退。
1944年3月28日，正当华西列夫斯基与马利诺夫斯基研究如何进攻敖德萨市时，接到了最高统帅斯大林打来的电话。在电话中，斯大林命令华西列夫斯基去见伏罗希洛夫元帅，同他商讨有关乌克兰第四方面军和濒海集团军，在克里米亚战役最初阶段中协同动作的问题。
斯大林还告诉华西列夫斯基，伏罗希洛夫将于3月29日10时，抵达克里沃罗格。
随后，华西列夫斯基从乌克兰第三方面军司令部，飞到了克里沃罗格。伏罗希洛夫元帅在他的车厢里接待了华西列夫斯基。
对于这次见面，华西列夫斯基许多年后，仍然记忆犹新。伏罗希洛夫一向很好客，而苏军对德军的巨大胜利，使这次会面更加愉快。伏罗希洛夫详细地向华西列夫斯基讲述了不久前结束的德黑兰会议的情况。
当然，他们主要谈论了与克里米亚战役有关的问题，决定让乌克兰第四方面军的首长参加到下一步的工作中来。为此，他们要在3月30日10时30分以前，转移到梅利托波尔。
3月30日，在进一步讨论关于克里米亚战役时，华西列夫斯基向伏罗希洛夫介绍了乌克兰第四方面军实施战役的计划。同时，伏罗希洛夫也向他们介绍了濒海集团军的行动计划。
濒海集团军准备突破敌军在刻赤以北的防御，一部分一部分地消灭敌军的刻赤集团，不让它退却到阿克—莫奈斯克阵地，而后向辛菲罗波尔—塞瓦斯托波尔发动突击，以一部分兵力沿克里米亚半岛南岸活动。
此外，他们还讨论了有关克里米亚战役最初阶段各部队协同动作的主要问题。参加这次研究工作的，还有乌克兰第四方面军军事委员苏鲍京、参谋长比留佐夫和空军第八集团军司令赫留金。
最后，华西列夫斯基和伏罗希洛夫根据研究结果，共同向斯大林提出一份实施克里米亚战役的综合报告。在报告中，他们提出：“如果天气允许，乌克兰第四方面军将不迟于1944年4月5日开始这一战役。我们建议刻赤方面在彼列科普战役开始后两三天内开始。”
3月30日夜，华西列夫斯基乘坐极有经验的驾驶员阿法纳西耶夫和他的领航员舍赫曼驾驶的飞机，从梅利托波尔回到了乌克兰第三方面军。在整个战争期间，华西列夫斯基多次乘坐他们俩驾驶的飞机，即使是在恶劣的天气条件下，他们也飞得很顺利。
4月8日，乌克兰第四方面军开始了进攻克里米亚半岛的战役。早晨，在方面军各部队宣读了关于转入进攻的命令：
我们在我们的父兄1920年洒满鲜血的土地上战斗，让我们的英雄主义把伏龙芝的军人的世界荣誉、俄罗斯武器的荣誉发扬光大吧！
4月11日，濒海集团军部队开始进攻。在整个战役的过程中，克里米亚的游击队给了苏军强有力的支援。
经最高统帅的允许，华西列夫斯基在敖德萨解放之后，于4月11日回到了乌克兰第四方面军司令部。当天，他就接到了大本营的命令。
根据苏联空军的侦察，获悉由于克列伊泽尔的第五十一集团军在赞科伊方向作战顺利，敌军已经由刻赤半岛开始撤退。于是，托尔布欣请求华西列夫斯基赶快让濒海集团军转入进攻。
华西列夫斯基支持这一请求，他马上将这一请求告诉了伏罗希洛夫。
4月10日，第五十一集团军突破了敌人的防御，从4月11日早晨起，坦克第十九军进入了突破口。该坦克军迅猛突击，进而占领了赞科伊。并通过克里米亚大草原，顺利地向辛菲罗波尔发起进攻。
在彼列科普附近，扎哈罗夫指挥的近卫第二集团军遭受敌军的顽强抵抗。华西列夫斯基与托尔布欣商量后，为了尽快夺取辛菲罗波尔，决定由坦克第十九军组成一个快速集群，由第五十一集团军副司令拉祖瓦耶夫少将指挥，其主要任务是在4月13日占领辛菲罗波尔。
4月11日傍晚，莫斯科为英勇的乌克兰第四方面军鸣放礼炮，祝贺他们突破了敌人在彼列科普和西瓦什湖的防御，并占领了赞科伊市。
4月12日这一天，乌克兰第四方面军解放了314个居民点，突破了卡尔基尼特湾以东的伊顺的阵地、以阿卡巴特列尔卡沙咀为依托的阿克—莫奈斯克的阵地，以及克里米亚中的比尤克—昂拉尔斯克的阵地。这时，全线展开了进攻。
4月13日，苏军胜利的旗帜飘扬在辛菲罗波尔、叶夫帕托里亚和费奥多西亚的上空。
4月15日，苏第五十一集团军的快速部队前出到了塞瓦斯托波尔的防御外廓，这是德军的最后希望所在，但是在苏军的猛烈打击下，希望破灭了。
为了表彰苏军杰出的战斗行动，最高统帅向辛菲罗波尔的解放者宣布嘉奖。首都莫斯科又为前线的英雄们鸣放了庆贺礼炮。
然而，紧张的战斗仍在进行着。
斯大林不止一次地提醒华西列夫斯基他们，必须尽快消灭敌军的克里米亚集团，而华西列夫斯基他们也很清楚这一点的重要意义，无论从军事观点还是从政治观点上来看，都是如此。
4月26日，华西列夫斯基与托尔布欣分析战局后，作出决定：将在30日使用近卫第二集团军在辅助方向实施突击，同时让近卫步兵第十三军越过麦肯齐耶维山进入战斗，前出到北海湾，把在南区作战的敌人兵力的一部分吸引过来。
预计在29日至30日凌晨，苏军所有的大口径火炮和152毫米加农榴弹炮、带有大型炸弹的远程航空兵、所有的加强兵器和作战飞机，都将投向德军防御阵地，以便掩护坦克部队和伴随其前进的步兵强攻封锁队的强攻。
至5月1日，再由第五十一集团军和濒海集团军从南面实施迂回，夹击城内敌军。同时，还需要调动克里米亚半岛上游击队参加辅助作战。
4月28日夜间，华西列夫斯基就这些计划，同斯大林进行了长时间的通话。斯大林对拟定的战役企图和兵力部署没有提出任何疑问，也未要求作重大的修正。
但是，当华西列夫斯基谈到进攻还要做新的延期时，斯大林就失去了平静，言辞变得十分得激烈。然而，华西列夫斯基没有放弃自己的意见。
最后得到最高统帅的批准：如果情况需要，将于5月5日由近卫军第二集团军在辅助方向发起进攻，而于5月7日以方面军的所有部队、黑海舰队和游击队的力量，对塞瓦斯托波尔的筑垒地域发动总强攻。
在接下来的几天里，各级指挥人员对他们的进攻地段进行了多次勘察，对地形和敌情作了详细的研究，并周密演练了完成当前任务的计划。此外，在苏军各部队后方修建了强攻教练场，以供在最大限度接近实战的条件下演练战斗动作。特别仔细地练习了步兵同炮兵、坦克和飞机的协同动作。
鉴于苏联游击队在1944年整个克里米亚战役期间所起的巨大作用，华西列夫斯基他们征得克里米亚州党委的同意，在5月3日，向国防委员会发出一份由乌克兰第四方面军首长和政治部积极参加制定的，呈请授予游击队运动参加者以政府奖励的文件：6人授予苏联英雄称号，14人奖励列宁勋章，17人奖以红旗勋章，23人奖以一级卫国战争勋章，63人奖以二级卫国战争勋章等。
5月5日，近卫第二集团军在两小时的炮火准备和航空兵突击之后，转入了进攻。
大威力火炮在冲击前夜和进攻当天的清晨，就用火力破坏永备防御工事。方面军的全部航空兵轰炸和扫射敌人的战斗队形，以及妨碍苏军步兵和坦克向前推进的敌军炮兵。战斗打得非常的激烈，在许多地段上都变成了肉搏战。
5月7日10时30分，在一个半小时的炮火准备后。在方面军全部航空兵的密集支援下，苏军对塞瓦斯托波尔筑垒地域发起了总强攻。德军的一段9公里防御阵地被突破，同时苏军还占领了萨彭山。
萨彭山的陷落，注定了塞瓦斯托波尔将被攻占。从该山山顶，以及从卡亚—巴什山，就可以观察全城以及直到赫尔松内斯角的一片平原。
5月9日8时整，乌克兰第四方面军向塞瓦斯托波尔再次发起总强攻。攻城战斗持续了一整天。日终时，苏军的部队前出到敌人预先构筑的从斯特雷列茨湾通向大海的防御地区。
前面是还在德军手中的克里米亚的最后一条狭长地段，即从奥麦加到赫尔松内斯角。
5月10日，被希特勒法西斯吹嘘为固若金汤的“堡垒城市”塞瓦斯托波尔，终于被苏军占领了。
同日清晨，最高统帅传来命令：
致苏联元帅华西列夫斯基、托尔布欣大将：
乌克兰第四方面军在航空兵和炮兵密集突击的支援下，经过三天进攻战斗，突破了德国人用三层钢筋混凝土防御工事构成的永备坚固的筑垒防御，并在几小时之前占领了黑海的要塞和极重要的海军基地——塞瓦斯托波尔城，从而清除了德国人在克里米亚的最后抵抗基地。
克里米亚的德国法西斯侵略者已彻底肃清。
在电报命令的后面，列举了所有在塞瓦斯托波尔战斗中表现突出的、报请授予塞瓦斯托波尔部队称号和勋章奖励的部队名单。
同日，首都莫斯科向解放塞瓦斯托波尔的乌克兰第四方面军部队，鸣放礼炮致敬。
5月11日夜间，濒海集团军和第五十一集团军突破敌人掩护赫尔松内斯角的防御地区，彻底肃清了敌军在塞瓦斯托波尔集团的残部，一昼夜之后，前出到黑海沿岸全线。
1944年5月12日，苏军在克里米亚的进攻战役结束。这次战役彻底粉碎了拥有20万人的德国第十七集团军，其全部的技术兵器和弹药都落入了苏军手中。
此时，华西列夫斯基的心情异常激动。他不禁想到：在1941年至1942年，德军和罗马尼亚军队围困塞瓦斯托波尔长达250天。而今，我们只用了35天，就突破了德军在克里米亚的坚固的防御工事。
其中，只经过了3天时间，就粉碎了塞瓦斯托波尔附近的、比苏军在1942年要完备得多的永备防御工事，解放了黑海舰队的主要基地。
首都莫斯科鸣放了五次礼炮，向把克里米亚从德军手中解放出来的陆海空战士们表示最诚挚的祝贺。
华西列夫斯基非常希望在解放塞瓦斯托波尔的第一天，到那里去看一看。
然而，很不走运的是，华西列夫斯基乘坐的越野车在麦肯齐耶维山地区，越过一条德军的堑壕时，触上了一枚地雷！
华西列夫斯基觉得很不可思议：这枚地雷如何还能完整地留在那里，因为在两昼夜的时间里，通过这里的已经有几百辆汽车了。
越野车轧到地雷上后，汽车的发动机和前轮被爆炸的气浪甩到离车身好几米远的地方，司机斯米尔诺夫中尉伤了左腿。
当时，华西列夫斯基同司机并排坐在驾驶室里，他的头部受了重伤，脸部被玻璃碎片划伤了。而护送华西列夫斯基的基亚尼茨基将军和格里年科、科佩罗夫两位副官因为坐在后面，没有受伤。
华西列夫斯基和司机在被扎上绷带后，送往集团军司令部的后方梯队，随后送往方面军司令部。由于医生的一再坚持，华西列夫斯基从那里乘坐飞机，被送往莫斯科。
