Изменение коллекционерских вкусов Костакиса произошло после Второй мировой войны, когда традиционное искусство начало приедаться. «Постепенно я стал уставать от всех этих серых и коричневых тонов, — рассказывал он мне однажды в полдень за чашкой очень крепкого черного кофе. — Мне захотелось видеть вокруг себя яркие краски. Яркое современное искусство действует на меня как лекарство. Когда я плохо себя чувствую, мне стоит лишь войти в комнаты и побыть там некоторое время в окружении моих картин, как я излечиваюсь. Кроме того, мне хотелось заняться чем-то новым. Ведь коллекционировать картины старых голландцев мог бы каждый. И я подумал про себя: «Лувр полон картин и в каждом городе есть по четыре-пять музеев классического искусства». А мне всегда хотелось сделать что-нибудь свое написать книгу, изобрести машину. И тут я случайно напал на две или три картины авангардистского направления. Они показались мне динамичными и красочными. Я приобрел их почти даром и повесил рядом с другими своими картинами. Эффект был таков, как будто постоянно темная комната внезапно озарилась солнцем».

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