Атомный подводный ракетный крейсер К-186 вступил в строй в декабре 1993 года. Он стал одним из первых подводных кораблей отечественного флота, которые в апреле того же года были именованы в честь городов России. Поскольку крейсер был предназначен в состав Тихоокеанского флота, он получил название в честь сибирского мегаполиса. За подлёдный переход "Омска" через Северный Ледовитый океан его командир Александр Сергеевич Астапов был удостоен звания Героя России.
Омская область шефствует над кораблём с 2001 года: оказывает его экипажу материальную помощь и направляет своих призывников служить на "Омске". Флаг представляет собой военно-морской Андреевский флаг, на который наложен герб города Омск, действовавший с 2002 до 2014 года.