Все же необходимость в регулярном морском сообщении на Севере оставалась столь насущной, что уже в следующем году, с весьма значительным финансовым участием государства, было образовано Товарищество Архангельско-Мурманского срочного пароходства. Две его линии охватывали Белое море, но третья связала губернский центр с норвежским портом Вардё. Поначалу на ней ходил изрядно потрепанный временем пароход «Онега». Он совершал за навигацию 13 каботажных рейсов. С марта — между Вардё через Екатерининскую гавань в Восточную Лицу, с июня до поздней осени — далее до Архангельска, заходя в восемь поселков. Позже Товарищество приобрело только что сошедшее со стапелей судно «Ломоносов» — 900 тонн водоизмещением и со скоростью 11 узлов. Оно позволило делать уже 27 рейсов, то есть каждую неделю, посещая по пути 18 поселков.
Только тем свою деятельность Товарищество не ограничивало. В Варангер-фьорде[7] для местных перевозок держало стотонное судно «Преподобный Трифон». Два раза в году, весной и осенью, один из его пароходов начиная с 1860 года ходил на Новую Землю, куда стараниями архангельского губернатора в 1877 году переселили 90 ненцев, обосновавшихся в трех становищах: Малые Кармакулы и Белушья Губа — на западном побережье южного острова, Маточкин Шар — у восточного выхода из пролива. А с 1895 года открыло четвертую линию — от Архангельска до устья Печёры, которую обслуживал пароход «Норденшельд». Наконец, купило сухогруз «Граф Литке», регулярно доставлявший из Англии уголь.
Развивали промыслы не только русские, но и норвежцы. Пользовались, правда, тем, что не существовало общепризнанных международных соглашений, устанавливавших морские экономические зоны и границы территориальных вод (условно определявшихся с молчаливого согласия всех стран в 3 мили — дальность пушечного выстрела с берега). Потому-то норвежцы и полагали Баренцево море открытым для себя при рыбной ловле, бое зверя. Промышляли не только у берегов Новой Земли, у острова Колгуева, но даже в горле Белого моря.
Чтобы хоть как-то отреагировать на многочисленные жалобы поморов, время от времени появлявшиеся в печати, Министерство внутренних дел в 1886 году передало в распоряжение архангельского губернатора пароход «Мурман». Предназначило его для контроля Кольским исправником соблюдения установленного порядка ведения промыслов и препятствования нарушениям закона со стороны судов, идущих под любым флагом. К сожалению, маломощная, всего в 30 лошадиных сил, машина «Мурмана» так и не позволила ему выполнить порученное весьма важное и ответственное задание.
Учитывая сложившееся положение, Главный морской штаб в 1891 году решил держать в Ледовитом океане военный корабль, который и патрулировал бы воды мурманского побережья. Но только два года спустя из Либавы в Баренцево море направили крейсер 2-го ранга «Наездник». В инструкции, врученной его командиру, указывалось: контролю и охране подлежат «территориальные воды — все заливы, бухты и рейды русского берега Ледовитого океана, все Белое море южнее линии, проведенной от Святого Носа к Канину Носу, на расстоянии в 3 мили, и Карское море в 3 милях от крайней береговой черты в малую воду (при отливе. —
Удачным оказался лишь первый поход. «Наездник» задержал в районе Иоканьги шесть норвежских промысловых судов и доставил их в Екатерининскую гавань. Кольский мировой судья признал виновными в нарушении российских законов шкиперов четырех судов и приговорил их к конфискации груза — более тысячи тюленьих шкур, жир, а также к выплате штрафа. Следует отметить, что дела эти рассматривались в каюте капитана «Наездника», ибо других подходящих помещений во всей округе не нашлось.
В последующие годы и с той же инструкцией в Баренцево море для патрулирования направлялись другие корабли Балтийского флота. В 1894 и 1895 годах — устаревшие крейсеры «Вестник», «Джигит», в 1896-м — военный транспорт, позднее гидрографическое судно «Самоед». А с 1897 года уже постоянно нес службу на Севере, оставаясь тем не менее в составе Балтийского флота, транспорт «Бакан» водоизмещением в 885 тонн, машины мощностью 835 лошадиных сил позволяли достигать скорости 11 узлов, на борту были установлены два 75-миллиметровых и два 47-миллиметровых орудия.