Первые здания комплекса были построены в 1897–99 г. петербуржскими архитекторами А. Ивановым (дом 1) и Н. Проскуриным (дом 2). Это были две отдельных постройки, разделенные началом Малой Лубянки, которые выкупившее огромный земельный участок Страховое общество «Россия» использовало как доходный дом.
После революции все здания были национализированы. В 1919 г. здания были переданы Центральному аппарату ВЧК, в дальнейшем они стали главными зданиями органов государственной безопасности.
В середине 1930-х для разросшегося аппарата строят новый корпус на углу Б. Лубянки и Фуркасовского переулка. Первоначально задуманное с участием академика И. Фомина здание должно было зеркально отражать завершенный в 1934 году комплекс общества «Динамо». Иван Фомин, приглашённый из Ленинграда, задумал комплекс, состоящий из семиэтажного административного корпуса с конторскими помещениями, девятиэтажного жилого дома и соединяющей их башни в 14 этажей.
Но реализован был проект архитекторов Аркадия Лангмана и Ивана Безрукова, примыкающий к корпусу 2 бывшего здания общества «Россия». Здание имеет скругленный угол, облицованный черным гранитом цоколь и лапидарный фасад. Выходящая на переулок стена расчленена треугольными лопатками. Это чуть ли не единственное его украшение.
В 1939–47 годах мастерская академика архитектуры А. Щусева перестроила 1 дом, заняв проезжую часть М. Лубянки. Квартал, таким образом, замкнулся, а часть улицы стала вторым внутренним двором комплекса.
Щусев решает новый фасад в большем масштабе, чем четырех-пятиэтажные здания «России», вместо их эклектичного декора и ориентации на северное барокко он использует привычный для сталинского времени итальянский декор.
В 1940-е годы проект Щусева не был воплощен до конца: тогда перестроили правую половину здания, возвели центральный вход и лоджию на уровне третьего и четвертого этажей. Но левая часть дома сохранила дореволюционный облик с надстройкой 1930-х годов.
Только в первой половине 1980-х годов по указу генерального секретаря ЦК КПСС Юрия Андропова этот анахронизм был устранен. Законченное здание на Лубянской площади перестало быть аскетичным и строгим, но получило торжественный, парадный облик.
В 1970-х годах по четной стороне Большой Лубянки было возведено еще одно многоэтажное здание, рядом уже в 2008-м появился дополнительный корпус с вертолетной площадкой на крыше.
