Детство Алексея прошло в тяжелые послереволюционные годы. Уже в 16 лет, в 1921 году, приписав себе полтора года возраста, он без ведома родителей записался на флот. Служил матросом на буксирном пароходе «Амстердам» при переходе группы речных судов Северным морским путем из Мурманска в Красноярск, в 1922 году поступил на судоводительское отделение Киевского водного техникума, в 1927 году окончил его и поступил в Ленинградский морской техникум водных путей сообщения. После окончания учебы в 1931 году и до 1934 года ходил в качестве штурмана, помощника капитана, старпома, капитана на кораблях Дальневосточного пароходства. С 1934 по 1940 год — Балтийского пароходства.

В 1936 году в качестве старшего помощника капитана ледокольного парохода «Анадырь» участвовал в особой экспедиции под руководством О.Ю. Шмидта по проведению эсминцев «Сталина и «Войков» из Кронштадта во Владивосток Северным морским путем. За успешное выполнение задания награжден орденом «Знак Почета» (Указ от 25 февраля 1937 года).

В 1937 году в должности старпома ледокольного парохода «Моссовет» Алексей Матиясевич участвовал в переходе из Мурманска в Петропавловск-Камчатский по Северному морскому пути за одну навигацию. На обратном пути шедший рекордными темпами пароход, взявший на Камчатке большой запас угля, по приказу руководства задержался во льдах для помощи другим судам, несмотря на благоприятные условия для завершения своего похода. В итоге «Моссовет» остался во льдах на зимовку вместе с ними. Учтя это, командование посчитало переход выполненным. Таким образом, были получены доказательства, что Северный морской путь проходим в обоих направлениях в течение одной навигации.

В мае—июле 1940 года участвовал в экспедиции по переводу закупленных в Голландии судов из Роттердама в Ленинград, во время этой командировки Голландия была захвачена гитлеровцами. В связи с оформлением документов у оккупационного правительства и установкой новой морской рации отправка судов сильно задержалась. Перед выходом в море немецкий офицер сообщил советским морякам радиочастоты для связи «в случае неприятностей». В пути караван, шедший с ясными обозначениями нейтральной страны, был обстрелян самолетом с британскими опознавательными знаками, но предложенными частотами советские моряки не воспользовались. Неизвестно, был ли это действительно британский самолет или имела место немецкая провокация.

В ноябре 1940 года тридцатипятилетний моряк с двадцатилетним стажем Алексей Матиясевич успешно прошел медкомиссию и был направлен на Высшие специальные курсы командного состава Краснознаменного учебного отряда подводного плавания (КУОПП) имени С.М. Кирова».

В свой первый боевой поход «Лембит» вышел 12 августа 1941 года. Экипажу тогда предстояло пройти под водой почти через все Балтийское море и поставить мины во вражеских водах, а затем по возможности топить фашистские суда торпедами.

Хорошо запомнилась старпому и первая подводная вахта: «Проверяю курс, внимательно слежу за глубиной погружения. Стараюсь запомнить и анализировать все происходящее на лодке — никакая теоретическая подготовка не может заменить практического плавания.

Ранее, плавая только над водой, мне не приходилось особенно считаться с некоторыми явлениями водной стихии. Известно, что вода в реках, морях и океанах имеет разную плотность. Вследствие этого у надводного судна при переходе из воды с одной плотностью в район с другой плотностью меняется осадка. Например, при выходе из реки в море осадка уменьшится, а при входе с моря в реку увеличится. При плавании же под водой, когда лодка внезапно попадает в слои воды с разной плотностью, зевать нельзя — можно провалиться на глубину, на которой корпус лодки подвергнется опасному давлению, или же, наоборот, лодка может, словно поплавок, выскочить на поверхность и обнаружить себя, чем нарушит свое основное тактическое превосходство — скрытность плавания.

Четвертый час мы шли на глубине 20 метров. Неожиданно лодка клюнула носом. Стрелка глубиномера полезла вверх. Рули переложили на полный угол. Но все же продолжали погружаться. Увеличили скорость хода — не помогает.

— Приготовить помпу из уравнительной за борт.

— Есть приготовить помпу из уравнительной за борт, — отрапортовал вахтенный трюмный Расторгуев.

— Пошел помпа!

Мерно загудел мотор. Вода из уравнительной цистерны откачивалась за борт. Стрелка глубиномера заколебалась и тронулась вниз.

— Стоп помпа! Ход — два узла! — управляясь рулями, медленно всплыли на прежнюю глубину.

Так моя первая подводная вахта показала, что не зря нас учили на приборах в специальном кабинете. С особой благодарностью вспоминаю опытного подводника, бывшего помощника командира знаменитой подводной лодки «Пантера» капитана 1-го ранга Александра Георгиевича Шишкина, читавшего курс управления подводной лодкой и тренировавшего нас на специальном тренажере».

Когда «Лембит» точно вышел на важную коммуникацию противника, командир лодки проверил расчеты и только тогда отдал команду: «По местам стоять, мины ставить!» Вот пошла первая мина с левого борта, затем вторая с правого. И поочередно все двадцать мин вышли из шахт.

Уже потом стало известно, что на выставленном «Лембитом» заграждении подорвались немецкое учебное судно «Дейчланд», транспорт с грузом железной руды и морской железнодорожный паром.

В последних числах августа 41-го «Лембит» участвовал в беспримерном по сложности и боевой обстановке Таллинском переходе кораблей Балтфлота из Таллина в Кронштадт. Затем выходил в боевые походы на постановку минных заграждений, нарушение морских сообщений противника и несение дозорной службы.

Алексей Михайлович, вспоминая сентябрьский поход 42-го, пишет: «Нам предстояло действовать на подходах к фарватерам, ведущим в финские шхеры Утэ и Чекарсарен, и в районе маяка Богшер. По этим путям шли подкрепления на финский фронт. А на рейде Утэ формировались караваны с грузами, идущими из Финляндии.

Еще в Кронштадте, когда я узнал о предстоящем районе боевых действий, меня стала преследовать мысль: надо проникнуть на этот рейд.

Прошли сутки нашего пребывания на позиции; ни судов, ни самолетов противника мы не обнаружили.

Я еще и еще много раз с циркулем в руках изучал рейд Утэ. Чертил курсы лодки и возможные варианты атаки. Получалось, что, если на рейде окажется несколько судов, стоящих на якоре, там негде будет и развернуться. Будь у нас кормовые торпедные аппараты, было бы куда проще: развернул лодку на выход, дал залп по цели — ив море. А у нас только носовые аппараты, и маневрировать после залпа в стесненной акватории чрезвычайно сложно. Взвесив все «за» и «против», решил, что задача все-таки выполнима. Уж очень хотелось исполнить желание всего экипажа — открыть боевой счет лодки».

Но сначала экипажу банально не везло: рейд, на который удалось проникнуть «Лембиту» с огромным риском, оказался пустым. Развернулись на обратный курс. И только к вечеру следующего дня обнаружили на горизонте два сторожевика и два тральщика. На этот раз не удалось сблизиться с ними на дистанцию торпедного залпа… Уже в сумерках обнаружили два транспорта в охранении двух тральщиков. Но и здесь незадача: «В перископ видно плохо. Всплывать на поверхность? Еще светло, лодка тотчас будет замечена. Стрелять по акустическому пеленгу? Велика дистанция. Все же мы пошли на сближение, однако суда через семь минут скрылись в шхерах».