최운해(崔雲海)의 본관은 통천(通川)이고, 자는 호보(浩甫)이며 호군(護軍) 최녹(崔祿)의 아들이다. 아버지의 전공(戰功)으로 공민왕 때 충용위산원(忠勇衛散員)에 기용되고, 여러 벼슬을 거쳐 전공총랑(典工摠郎)이 되었다. 최윤덕(崔潤德)을 비롯하여 아들 넷을 두었다.
1385년(우왕 11) 10월, 충주병마사(忠州兵馬使)로서 왜구를 무찔렀다. 그 뒤 순흥 ‧ 영주등처조전병마사(順興榮州等處助戰兵馬使) 겸 경상도병선도관령사(慶尙道兵船都管領事)가 되어 수차례 왜구를 격퇴하였고, 이후 순흥부사(順興府使)에 임명되었다. 이때 왜구가 객관(客館)에 웅거하며 매일 침략하자 이를 격퇴하고, 노획한 우마(牛馬)와 재화(財貨)를 병사와 주민에게 나누어 주었으며, 또 굶주리는 백성을 잘 구호해 칭송을 받았다. 이러한 전공으로, 관직의 등급을 뛰어넘어 전법판서(典法判書)에 임명되었다.
왜구가 다시 원주, 충주, 단양, 제천 등지에 쳐들어오자 조전도병마사(助戰都兵馬使)가 되어 이를 물리치고 충주목사(忠州牧使)에 임명되었다. 전주목사(全州牧使)를 거쳐 밀직부사(密直副使)에 임명되었고, 충근좌명공신(忠勤佐命功臣)의 호를 받았다. 그 뒤 양광도 ‧ 광주등처절제사(楊廣道廣州等處節制使) 겸 판광주목사(判廣州牧使)로 왜구를 물리쳐 전공을 세웠다.
1388년(우왕 14) 4월, 요동 정벌군이 출정할 때, 전라도부원수(全羅道副元帥)로서 좌군도통사(左軍都統使) 조민수(曹敏修)에게 소속되어 정벌전에 참여했다. 5월, 이성계 등의 정벌군이 위화도(威化島)에서 회군할 때 함께 하여, 이후 1390년(공양왕 2) 4월, 광주등처병마절제사(廣州等處兵馬節制使)로서 회군에 참여한 공신으로 녹훈(錄勳)되었다. 회군이 모든 정벌군의 적극적 동의 속에 이루어진 것은 아니었으며, 회군 이후에도 회군공신을 책봉하는 것에 대해서는 반대 여론이 있었던 만큼, 회군공신의 책봉은 회군 이후 몇 차례 정치적 숙청이 이어진 이후에 행해졌다. 최운해가 여기에 포함된 것을 통해 그가 정벌군의 구성에서는 조민수에게 소속되어 있었으나, 이성계 세력의 회군 결정과, 그후 최영과의 대치 상황 등에서 이성계 측에 섰음을 추측할 수 있다. 회군 후, 같은 해 왜적이 3도(道)를 침략했을 때, 안주도도원수(安州道都元帥)로서 이성계에게 소속되어 요동 정벌전에 나섰다가 회군에 참여한 정지(鄭地)를 비롯한 이들과 함께 왜적을 격파하였다.
1392년(태조 원년) 조선 건국 후, 개국원종공신(開國原從功臣)이 되었고, 이듬해 문하평리(門下評理) 및 양광도절제사(楊廣道節制使)로서 박위(朴葳) 등과 함께 왜구를 격파하였다.
1396년(태조 5) 지중추원사(知中樞院事)로서 경상도병마도절제사(慶尙道兵馬都節制使)가 되어 영해(寧海: 현 경상북도 영덕군)에서 왜구를 격퇴하고, 지중추부사(知中樞府事)가 되었다. 한편, 1397년 항복했던 왜구들이 지울주사(知蔚州事) 이은(李殷)을 비롯한 이들을 납치해 간 사건이 폭로되어 청해도수군(靑海道水軍)에 충군(充軍)되었다.
그 뒤 풀려나와 1399년(정종 1) 전라도조전절제사(全羅道助戰節制使)로서 왜구를 방어하였다. 이듬해에는 참판삼군부사(參判三軍府事)로 예문관학사 송제대(宋齊岱)와 함께 남경(南京)에 다녀오다가 서원군(瑞原郡)에서 군수 박희무(朴希茂)를 구타했는데, 이 사건으로 한때 음죽(陰竹: 현 경기도 이천시)에 유배되었다.
1402년(태종 2)에는 이성도절제사(泥城道節制使)로 태조를 시위하였고, 강계안무사(江界安撫使)와 서북면순문사(西北面巡問使)를 거쳐 참판승추부사(參判承樞府事)로 사직하였다. 특히 왜구를 무찔러 여러 번 공을 세운 바 있어 명장의 칭호를 얻었다.
시호(諡號)는 양장(襄莊)이다.