История храма мучеников бессребреников Кира и Иоанна начинается не ранее второй половины XVI века. Храм был основан в непосредственной близости от более древней церкви мученицы Параскевы Пятницы на Кулишках, известной по описанию пожара 21 июня 1547 года. Она упоминается в Никоновской летописи среди сгоревших храмов: "... а Варварьскою улицею Всѣ Святые и святаа Пятница и Рожество Пречистые и Никола Подкопаевъ и Ѳлоръ Святый у конюшни, и конюшня великого князя, и по Воронцовьской дворъ и по Илію Святаго подъ Сосенки..."
Судя по тому, что церковь Кира и Иоанна, которая стояла в нескольких саженях от церкви Параскевы Пятницы, не упомянута в этом списке, её в это время не существовало. Впервые она упоминается в делах Патриаршего приказа в 1624/25 году. Таким образом, к этому времени на смежных участках существовали три храма (ещё церковь Всех святых на Кулишках).
Для создания церкви в таком тесном соседстве могло быть несколько причин. Возможно, это было связано с необходимостью иметь тёплую деревянную зимнюю церковь при холодной каменной. Так, в Переписной книге Белого города, составленном после пожара в апреле 1629 года, рядом почти с каждым каменным храмом упомянут деревянный. Однако церковь Кира и Иоанна не могла быть зимней для храма Параскевы Пятницы, потому что уже в начале XVII века каждая из них имела отдельный причт и отдельный приход. Церковь Кира и Иоанна могла быть построена владельцем одного из частных дворов, примыкавших к церковной земле храма Параскевы Пятницы. Подобных примеров в Москве было достаточно много.
Кроме того, само посвящение Киру Александрийскому и его ученику Иоанну, которые почитались как безмездные врачи и целители, было редким для Москвы и могло быть поставлено по обету за исцеление от болезни.
Посвящение могло быть связано и с находившейся неподалеку богадельней на Кулишках. Устройство этой богадельни относится к началу царствования Бориса Годунова, когда в 1599/1600 году были "взяты изо Пскова к Москве из богадельны три старицы миряне, устраивати богадельны по псковскому благочинию... И на Москве поставлены три богадельны: у Моисея пророка на Тверской улице богадельня, а в ней были нищие миряне; да богадельна против Пушечново двора, а в ней инокини; да богадельна на Кулишках, а в ней нищие, женской пол" (Пискаревский летописец).
По свидетельству Строельной книги 1657 года обе церкви - Параскевы Пятницы и Кира и Иоанна - были каменными. Кроме земли под храмом и кладбищем, церкви Кира и Иоанна принадлежал участок "порозжей" на земли на другой стороне Большой Мостовой улицы, где во время морового поветрия 1654 года были "кладены усопшие и то кладбище огорожено надолбами изредка".
В 1693 году храм был перестроен, в 1754-м горел, в 1758-м возобновлён.
В 1764 году Екатерина II повелела разобрать имеющих храм и поставить новый в честь того, что в день памяти Кира и Иоанна, 28 июня 1762 года, она взошла на престол.
Новое здание построил архитектор Карл Иванович Бланк, строивший и рядом находящийся Воспитательный дом.
Для посещения государыни и в ее честь в храме устроили особое царское место, которое хранилось тут до революции как памятная достопримечательность. По окончании праздничного богослужения императрица немедленно отбыла в Санкт-Петербург. В 1812 году солянский храм пострадал от наполеоновских солдат, но был восстановлен. В отличие от церкви Параскевы Пятницы, которую к тому времени уже освятили в честь Святой Троицы.
Несмотря на то, что храм Кира и Иоанна был построен по повелению императрицы, ризница его была скудной; утвари, облачений, икон было недостаточно. Исправить положение помогла эпидемия 1771 года. Опустел соседний храм Николая Чудотворца в Мыльниках, откуда и передали и утварь, и образ Девяти мучеников, и даже колокола. Интересно, что описывая переданное паникадило, писец назвал страфокомилово (страусиное) яйцо, подвешенное к паникадилу, крокодиловым.
С 1874 по 1918 гг в храме находилось подворье Сербского митрополита. Храм был закрыт в 1932 году и вскоре разрушен. На его месте поставили одноэтажный павильон с магазином "Кулинария", рядом - ларёк "Вино". От храма остался лишь столб ограды XVIII века.
