В течение 1990-х галерея сменила несколько имен, прошла через ряд изменений художественной стратегии, замещений и пополнений круга постоянных авторов. Галерея «Крокин» ведёт отсчёт своей деятельности с 1990 года, когда её основатель Михаил Крокин организовал выставку в арендованном зале Культурного центра на Петровских линиях. Один из участников выставки, художник Владимир Самсонов, подарил символическое название экспозиции, впоследствии ставшее именем Ассоциации художников «Нео-шаг». В начале 1990-х галерея держалась в стороне от радикальных форм современного искусства, представляя живопись с элементами декоративности, сюрреализма, беспредметности и наива.
Деятельность галереи «Нео-шаг» не ограничивалась Москвой: в 1992 году была организована выставка в женской исправительной колонии Можайска, а в первой половине 1990-х действовал филиал галереи в Санкт-Петербурге, где в 1993–1994 годах галерея издавала газету «Большая прогулка», посвящённую культурной жизни обеих столиц. «Нео-шаг» была одной из первых отечественных галерей, допущенных к участию в европейских и американских ярмарках. Опыт зарубежных выставок привел к смене названия по причине случайного совпадения с неблагозвучным англоязычным выражением. В 1997 году галерея изменила имя и место работы — теперь это галерея «Новая коллекция», открывшаяся в залах на улице Большая Полянка. В 2001 году «Новая коллекция» была переименована в галерею «Крокин».
Для политики галереи переломными были 1996–1997 годы. Именно тогда Михаил Крокин познакомился с такими современными художниками, как Франциско Инфантэ, Александр Константинов, Владимир Куприянов, Александр Мареев, Антон Ольшванг, Александр Пономарев и Ольга Чернышёва. Тогда же в галерее начал работать художник и искусствовед Александр Петровичев, который стал постоянным куратором «Новой коллекции» и галереи «Крокин». Новые имена постепенно возникали на выставках галереи, приобретавших всё более экспериментальный и исследовательский характер. По словам Михаила Крокина, в фокус его экспозиционной стратегии входят проекты, созданные художниками специально для пространства галереи, а также демонстрирующие новые и нетипичные черты работ уже известных авторов.