29 сентября 1893 года «Ревельские новости» сообщили, что в местечке Билдерлингсгофе (ныне город Балдераи) около Риги в море была найдена бутылка с запиской на русском языке, подписанная матросом Фреловым с «Русалки». В записке сообщалось время катастрофы — 9 часов 45 минут вечера и говорилось, что броненосец наскочил на камень. Спустя три дня в редакцию «Ревельских новостей» пришло письмо, подписанное литерой «Н». Аноним сообщал, что это он в состоянии подпития написал записку и выбросил ее в море. Газета отнесла данную историю в разряд курьезов. Однако, как выяснилось, в составе команды был матрос по фамилии Фролов, к тому же время и обстоятельства гибели «Русалки» были вполне реальными. Об истории с найденной бутылкой вскоре забыли, однако до сих пор вопрос о том, была ли это мистификация или записку писал все же матрос с «Русалки», остался невыясненным.
Разумеется, почти сразу же после известия о гибели балтийского броненосца в адрес Морского министерства начала поступать масса предложений о помощи в поиске и поднятии «Русалки». В журнале «Морской сборник» за февраль 1894 года была опубликована статья штабс-капитана Золотухина «О средствах, предложенных для отыскания броненосца „Русалка“». В ней автор предложил использовать для комбинированного поиска тралы нескольких конструкций одновременно. Еще один автор «Морского сборника» предложил искать «Русалку» с помощью магнитной стрелки, реагирующей на большую массу металла, находящегося на дне. По задумке автора этого проекта, надо было дождаться времени, когда Финский залив покроется льдом, и на санях объехать весь залив. Где стрелка поднимется в вертикальное положение, там и следует весной искать затонувший броненосец. Некий мещанин Фрумкин рекомендовал для поиска броненосца делать химический анализ воды. На дно следовало опускать бутылку с открывающимся горлышком и зачерпывать ею придонную воду. Затем эту воду надлежало подвергать анализу на предмет нахождения в ней частичек ржавчины. Где процент ржавчины будет более всего, там и следует искать пропавшую «Русалку». Кто-то предлагал вооружить тралами весь Балтийский флот и протралить им всю водную поверхность между Ревелем и Гельсингфорсом. Другие советовали обратиться к Николе Угоднику, и любимый морской святой непременно укажет место гибели корабля.
Несмотря на неудачу поисковых работ осенью 1893 года, с началом навигации следующего, 1894 года поисковые работы были возобновлены. Для поиска «Русалки» было решено использовать все технические новинки того времени. Организованной еще зимой поисковой партии на это раз были даны рекомендации министерства: Во-первых, необходимо было тщательно обследовать водное пространство на три с половиной морские мили к северу, востоку и югу от маяка Эрансгрунд и на три четверти мили к западу от него (в министерстве считали, что именно этот район является наиболее вероятным местом гибели «Русалки»). Во-вторых, следовало осмотреть водолазам и обследовать тралами все пространство у камней и островов в окрестностях Гельсингфорса. Предполагалось, что «Русалка» могла затонуть в результате удара о камни у входа в финские шхеры. Общее руководство всеми поисковыми работами было возложено на командира Свеаборгского порта капитана 1-го ранга Вишнякова. К огромному неудовольствию газетчиков, на этот раз все поисковые работы во избежание появления всевозможных слухов предполагалось проводить при минимальной огласке.
Тральное дело тогда еще пребывало в самом зачаточном состоянии. На вооружении всех флотов мира состояли самые примитивные тралы. Между двумя судами закрепляли проволочный трос длиной 213 метров. Затем оба судна давали одинаковый ход и тащили за собой образовавшуюся петлю. При задевании троса за какое-либо препятствие суда останавливались и выясняли причину. Участвовавший в этом тралении лейтенант В.И. Ларионов (впоследствии участник Цусимского сражения на броненосце «Орел») вспоминал: «Тралили собственно не очень-то старательно и даже недобросовестно, так как пароходы не шли строго по вехам, а стало быть, оставляли мертвые пространства, а к тому же частенько подтягивали середину трала ближе к корме, чем бы это следовало». Водолазы, обследовавшие прибрежную часть предполагаемого района катастрофы с парохода «Буксир», тоже ничего не обнаружили. К тому же тогдашнее развитие водолазного дела не позволяло опускаться ниже 53 метров.