В 1990-м году на первой полосе газеты «Комсомольская правда» было опубликовано фото молодой женщины, позирующей с пистолетом, под заголовком «Мисс КГБ». Правда, когда и где проходил конкурс на это звание, а также кто ещё, кроме Кати Майоровой, в нём участвовал, осталось неизвестным.
В интервью корреспонденту газеты «Вашингтон Пост» Дэвиду Ремнику Майорова намекнула, что её появление в газете — пиар-ход советских спецслужб: «Мы не хотим, чтобы люди думали, что мы здесь какие-то монстры» — объяснила она. Не факт, что Майорова вообще когда-либо работала в КГБ, но «она играла роль королевы красоты самоотверженно: улыбалась и кокетничала, отвечая на вопросы, и позировала с бюстом Дзержинского» — написал Ремник в своей статье.