Приблизительно в это же время проявился его инстинкт коллекционера. У его шурина, члена аристократической греческой семьи Метаксас, был набор редких марок, которые он оставил своей вдове. Никто не увидел в них особой ценности, и марки отдали юному Георгию, который тут же помчался обменять их на деньги, чтобы купить себе велосипед. Он был поражен, когда у магазина марок некий японский турист «отдал мне все деньги из своего кошелька — а этого хватило бы на шесть велосипедов». К 22 годам Костаки уже серьезно коллекционировал антиквариат, старинное русское серебро и картины традиционных французских и голландских мастеров. В предвоенный период, когда семьи бывшего дворянского сословия, лишенные состояния, распродавали свои произведения искусства, Москва была полна сокровищ по бросовым ценам.
Кардинальные перемены в жизни Костаки произошли после Второй мировой войны, когда традиционное искусство начало приедаться. «Постепенно я устал от этих серых и коричневых тонов, — объяснил он мне однажды днем за чашкой очень крепкого черного кофе. — Я хотел, чтобы вокруг меня было немного цвета. Яркое современное искусство для меня как лекарство. Если мне плохо, я могу войти в комнату, посидеть в его окружении, и оно исцелит меня. Кроме того, я хотел сделать что-то новое. Я знал, что любой мог коллекционировать голландских мастеров. Я подумал про себя: „Лувр уже полон, и в каждом городе есть четыре или пять музеев классического искусства“. А мне всегда хотелось чем-нибудь заняться — написать книгу, изобрести машину. Потом я случайно наткнулся на две или три авангардные картины. Для меня они были динамичными и красочными. Я получил их даром и поместил вместе с другими моими картинами, и это выглядело так, как если бы я жил в темной комнате и вдруг в нее вошло солнце».
Он был не только необычным и смелым, но еще и везучим. Это была эпоха, когда сталинский приспешник Андрей Жданов энергично искоренял формализм и либерализм во всех сферах искусства. «Глупый грек — коллекционирует хлам!» — так, по воспоминаниям Костаки, говорили тогда о нем другие коллекционеры. Подобно детективу, он стал искать произведения авангарда. Одни картины принадлежали вдовам и семьям художников. Другие, как и работа его любимицы Ольги Розановой, были подарены ему коллекционерами, не знавшими, куда деть этот абстракционизм. Родченко сделал шесть модернистских мобилей, но, опасаясь разоблачения при Сталине, уничтожил пять из них. Шестой выжил, спрятавшись и рассыпавшись со временем на шкафу, и Костаки забрал его себе. Абстракция Поповой, нарисованная на фанере, годами висела в сарае. Еще одна картина лежала под клеенкой на чьем-то кухонном столе, спрятанная либо по незнанию, либо осознанно.
Когда Костаки приходилось платить, он покупал по очень выгодным ценам. Большая кубистско-супрематическая работа Малевича, которая сейчас стоит, возможно, полтора миллиона долларов, обошлась ему примерно в 400 долларов. Столько же он заплатил за прекрасный натюрморт Шагала «Сирень на столе», и вдвое меньше — за кубистическую работу Поповой. Он объяснил, что это были годы, когда такие имена, как Кандинский и Шагал, были известны, но не до конца оценены и когда он сам стал отходить от тех, кого ему нравится называть маршалами и генералами русского авангарда, чтобы «найти полковников, капитанов и рядовых». В целом, по его оценкам, с 1910 по 1925 год в авангардном движении приняли участие примерно 300 художников, и около 40 из них есть в его коллекции.
С точки зрения Запада, в этом искусстве нет ничего политически провокационного, за одним исключением, хотя советские консерваторы могут найти мятежный замысел во всем неортодоксальном. Это поразительное исключение — пророческое кафкианское полотно под названием «Восстание», созданное Климентом Редько в год смерти Ленина. С жутковатыми подробностями оно одновременно передает и красный террор, и грядущее единообразие сталинского тоталитаризма, и только что прошедшую Гражданскую войну. Как на политической иконе, на кроваво-красном фоне картины выстроились ромбом главные фигуры революции — Ленин, Сталин, Троцкий, Бухарин и другие. Вокруг этого центра движутся мрачные похоронные оркестры и грузовики с войсками, стреляющими друг в друга… Единственное заметное политическое настроение в коллекции, если таковое вообще имеется, — это бьющий через край идеализм художников революционного периода. И все же коллекция пребывает в своеобразном советском чистилище.