Ocean Discoveryのダイバーらは1990年代の初めから捜索を開始し、1999年にはエコーサウンダーからサイドスキャンソナーへのアップグレードを実施した。当時の文献が正確さを欠いたものであったため、チームは15平方マイル（約38.8平方キロメートル）という比較的広大な領域を調査するとともに、地元の漁師からマルス号の沈没地点の謎を解く鍵になるかもしれない遺物が底引き網にかかった場所の情報を聞き出し、マルス号発見の望みを託していた。
バルト海は水温が低く、水没した木材を食い荒らすフナクイムシも生息していないという特殊な環境であるため、この海に沈んだ船の保存状態は良好なものとなる。Ocean Discoveryのチームは、漁師が底引き網で回収した残骸の情報に基づいた調査を通じて、バルト海に沈んでいる数多くの木造船が良好な状態で保存されていることを確認した。しかし、漁師からの情報で得られた場所に沈んでいた船はいずれもマルス号ではなかった。
チームは、歴史的文献と漁師からの情報をあきらめ、サイドスキャンソナーを東に西にえい航し、該当地域をくまなく探査した。
2011年のある日、チームはサイドスキャンソナーに通常とは違ったマストのような映像を見つけたため、数時間をかけてがれきの散乱状況を調査していた。Ingemar Lundgren氏は「半分ほど過ぎたところで、われわれは沈没船にしか見えない物体を見つけた」と述べた。40mにおよぶ船体が姿を現した。チームは、スウェーデンのエリク14世の艦隊の旗艦をついに発見したのだった。
Rönnby氏は「（マルス号の残骸であると判断するに至った）最初の特徴は、そのがれきの規模の大きさだ。それは海底で本当に大きな存在感を放っていた。サイドスキャンソナーの映像でも非常に大きな残骸であることが分かった。最初に画像を見た際、われわれはこの船の（建造）技術に気がついた（中略）これはさまざまな点でメアリーローズ号とよく似ていた。その後、この残骸がマルス号のものであると判断できる証拠が現れた」と述べた。メアリーローズ号は16世紀のイングランド王国の戦艦であり、ヘンリー8世の艦隊の旗艦だったが、マルス号が沈没する約20年前の1545年に海の底に沈んでおり、マルス号の発見に先立つ約30年前、すなわちに1982年に残骸が引き上げられていた。
マルス号を発見した際、Richard Lundgren氏とFredrik Skogh氏、Christoffer Modig氏、Anton Petersson氏からなる4人のチームが調査船に乗り込んでいた。彼らはソナー映像を、陸上で映像分析を行っているIngemar Lundgren氏に送った。同氏は「それが今までのものとはあまりにも違っていたので、おそらくマルス号だろうと答えた」と述べた。
とは言うものの、最初に発見されてからその出自の確定までにはしばらく時間がかかった。Lundgren氏は「サイドスキャンソナーは現在利用可能な最高の技術だが、大砲のような装備を識別できるだけの詳細な解像度は持ち合わせていない。これはどちらかというと位置を特定するための技術であり、海洋考古学の調査を行う技術ではない」と述べた。
