王鎮惡，北海劇人也。祖猛，字景略，苻堅僣號關中，猛為將相，有文武才，北土重之。父休，為河東太守。鎮惡以五月五日生，家人以俗忌，欲令出繼疏宗。猛見奇之，曰："此非常兒，昔孟嘗君惡月生而相齊，是兒亦將興吾門矣！"故名之為鎮惡。年十三而苻氏敗亡，關中擾亂，流寓崤、澠之間。嘗寄食澠池人李方家，方善遇之。謂方曰："若遭遇英雄主，要取萬戶侯，當厚相報。"方答曰："君丞相孫，人才如此，何患不富貴。至時願見用為本縣令，足矣。"後隨叔父曜歸晉，客居荊州。頗讀諸子兵書，論軍國大事，騎乘非所長，關弓亦甚弱，而意略縱橫，果決能斷。
廣固之役，或薦鎮惡於高祖，時鎮惡為天門臨澧令，即遣召之。既至與語，甚異焉，因留宿。明旦謂諸佐曰："鎮惡，王猛之孫，所謂將門有將也。"即以為青州治中從事史，行參中軍太尉軍事，署前部賊曹。拒盧循於查浦，屢戰有功，封博陸縣五等子。高祖謀討劉毅，鎮惡曰："公若有事西楚，請賜給百舸為前驅。"義熙八年，劉毅有疾，求遣從弟兗州刺史藩為副貳，高祖偽許之。九月，大軍西討，轉鎮惡參軍事，加振武將軍。高祖至姑孰，遣鎮惡率龍驤將軍蒯恩百舸前發，其月二十九日也。戒之曰："若賊知吾上，比軍至，亦當少日耳。政當岸上作軍，未辦便下船也。卿至彼，深加籌量，可擊，便燒其船艦，且浮舸水側，以待吾至。慰勞百姓，宣揚詔旨並赦文、及吾與衛軍府文武書。罪止一人，其餘一無所問。若賊都不知訊息，未有備防，可襲便襲。今去，但云劉兗州上。"鎮惡受命，便晝夜兼行，於鵲洲、尋陽、河口、巴陵守風凡四日；十月二十二日，至豫章口，去江陵城二十里。
自鎮惡進路，揚聲劉兗州上，毅謂為信然，不知見襲。鎮惡自豫章口舍船步上，蒯恩軍在前，鎮惡次之。舸留一二人，對舸岸上豎六七旗，下輒安一鼓。語所留人："計我將至城，便長嚴，令後有大軍狀。"又分隊在後，令燒江津船艦。鎮惡徑前襲城，語前軍："若有問者，但云劉兗州至。"津戍及百姓皆言劉藩實上，晏然不疑。
未至城五六里，逢毅要將朱顯之，與十許騎，步從者數十，欲出江津。問是何人，答云："劉兗州至。"顯之馳前問藩在所，答云："在後。"顯之既見軍不見藩，而見軍人擔彭排戰具，望見江津船艦已被燒，煙焰張天，而鼓嚴之聲甚盛，知非藩上，便躍馬馳去告毅："外有大軍，似從下上，垂已至城，江津船悉被火燒矣。"行令閉諸城門。鎮惡亦馳進，軍人緣城得入，門猶未及下關，因得開大城東門。大城內，毅凡有八隊，帶甲千餘，已得戒嚴。蒯恩入東門，便北回擊射堂，前攻金城東門。鎮惡入東門，便直擊金城西門。軍分攻金城南門，毅金城，內東從舊將，猶有六隊千餘人，西將及能細直吏快手，復有二千餘人。食時就斗，至中晡，西人退散及歸降略盡。鎮惡入城，便因風放火，燒大城南門及東門。又遣人以詔及赦文並高祖手書凡三函示毅，毅皆燒不視。金城內亦未信高祖自來。有王桓者，家住江陵，昔手斬桓謙，為高祖所賞拔，常在左右。求還西迎家，至是率十餘人助鎮惡戰。下晡間，於金城東門北三十步鑿城作一穴，桓便先眾入穴，鎮惡自後繼之，隨者稍多，因短兵接戰。鎮惡軍人與毅東來將士，或有是父兄子弟中表親親者，鎮惡令且斗且共語，眾並知高祖自來，人情離懈。一更許，聽事前陣散潰，斬毅勇將趙蔡。毅左右兵猶閉東西閣拒戰，鎮惡慮暗夜自相傷犯，乃引軍出，繞金城，開其南面，以為退路。毅慮南有伏兵，三更中，率左右三百許人開北門突出。初，毅常所乘馬在城外不得入，倉卒無馬，毅便就子肅民取馬，肅民不與。朱顯之謂曰："人取汝父，而惜馬不與，汝今自走，欲何之？"奪馬以授毅。初出，政值鎮惡軍，沖之不得去；回沖蒯恩軍，軍人斗已一日，疲倦，毅得從大城東門出奔牛牧佛寺，自縊死。鎮惡身被五箭，射鎮惡手所執槊，於手中破折。江陵平後二十日，大軍方至。
署中兵，出為安遠護軍、武陵內史。以討劉毅功，封漢壽縣子，食邑五百戶。蠻帥向博抵根據阮頭，屢為凶暴，鎮惡討平之。初行，告刺史司馬休之，求遣軍以為聲援，休之遣其將朱襄領眾助鎮惡。會高祖西討休之，鎮惡乃告諸將曰："百姓皆知官軍已上，朱襄等復是一賊，表里受敵，吾事敗矣。"乃率軍夜下，江水迅急，倏忽行數百里，直據都尉治。既至，乃以竹籠盛石，堙塞水道。襄軍下，夾岸擊之，斬襄首，殺千餘人。鎮惡性貪，既破襄，因停軍抄掠諸蠻，不時反。及至江陵，休之已平，高祖怒，不時見之。鎮惡笑曰："但令我一見公，無憂矣。"高祖尋登城喚鎮惡，鎮惡為人強辯，有口機，隨宜酬應，高祖乃釋。休之及魯宗之奔襄陽，鎮惡統蒯恩諸軍水路追之，休之等奔羌，鎮惡追躡，盡境而還。除游擊將軍。