Здание гостиницы было построено в 1960 году. Это одно из первых каменных зданий в столице Республики. Сначала данное здание должно было быть в три этажа. В самый последний момент было принято решение надстроить еще один этаж. Первоначально в гостинице было 154 комнаты. Они были очень маленькие и без собственного санузла. Гостиница в то время получила название «Лена» — в честь реки протекающей в городе Якутске.
В 2000м году здание было приватизировано. В 2004 была проведена первая реновация. Был сделан современный по тем меркам «евроремонт». В отеле расширили комнаты, их стало 51. Отель получил название «Стерх». Стерх — это священная для народа Саха птица, широко воспетая в стихах и песнях, а также в изобразительном искусстве и народном творчестве.
В 2022 году пришло время новой реновация гостиницы. В этот раз в гостинице были заменены все коммуникации, измен номерной фонд. При ремонте использовались только экологически чистые материалы, современные технологии. Установлена комфортная, удобная мебель, немецкая и турецкая сантехника от лидеров рынка, шикарные матрасы. Дизайнер постаралась собрать в себя не только современный стиль, но при этом подчеркнуть наши особенности, позволить гостю прикоснуться к культуре Республики Саха (Якутия). Сейчас в гостинице 49 номеров. Мы сделали их разными по дизайну, чтобы гостям было не скучно проживать в гостинице. Мы уверены, что каждый найдет что-то свое.
В гостинице также появились тренажерный зал и комната переговоров. В коридоре на 4м этаже представлена выставка картин «Мир в лицах» фотохудожника из Якутска — Александра Химушина, которые выставлялись в ООН. К сожалению, из-за конструктивных особенностей нашего здания не удалось установить лифт.