После открытия кинотеатр был рассчитан на 630 мест и располагал большим фойе с антресолями. Была предусмотрена эстрадная площадка, на которой играл симфонический оркестр, преподавателями уфимских ВУЗов и лекторами читались лекции. Был читальный зал. Здание украшала фигура воина-победителя. В 1958 г. кинотеатр «Победа» стал широкоэкранным.
В 2000—2001-х гг. проходил реконструкцию во время которой обветшавшее здание было отремонтировано, а проекционное и звуковое оборудование и экран — заменены. В зале установлен перламутровый экран, звуковая система Dolby Digital и цифровое оборудование для демонстрации фильмов в формате 3D. Сам зал рассчитан на 368 зрителей. Тогда же с фронтона была убрана скульптура воина.
26 октября 2016 года скульптурную композицию отлили заново и вернули на прежнее место. Скульптор Халит Галиуллин.
23 июля 2017 года прошёл последний сеанс, кинотеатр закрыт в связи с убыточностью в течение последних нескольких лет.
В августе 2017 года появилась информация о продаже кинотеатра из-за долгов владельца кинокомплекса, который, взяв в кредит у «Регионального фонда» республики 60 млн рублей, заложил здание кинотеатра, но расплатиться с фирмой так и не смог. По решению суда «Победу» выставили на торги, но новый собственник объекта так и не нашелся.
В январе 2019 года появилась информация о передачи «Региональным фондом» здания в собственность мэрии города. Мэрия в свою очередь намерена переселить туда детскую юношескую спортивную школу № 22.