Первая выставка передвижников была устроена в 1871 году. Все, что было в Петербурге передового, прогрессивного, только и говорило в эти дни о выставке и картинах Крамского, Мясоедова, Ге, Перова.
Одним из первых попал на выставку и Костычев. Он ее осматривал не один раз. Огромное впечатление произвела на него картина Мясоедова из крестьянской жизни — «Страдная пора» — и особенно «Чтение «Положения 19 февраля». Костычев еще яснее понял, как злодейски был обманут и обворован народ в результате пресловутой крестьянской реформы.
В это время Костычев повстречал молодую девушку Авдотью Николаевну Фокину. Она ему очень понравилась. Их интересы во многом оказались общими. Авдотья Николаевна тоже любила живопись, но только живопись «идейную». Она осуждала старое, «академическое» направление, далекое от народа, и восторженно приветствовала передвижников. Девушка была очень начитана: знала многие произведения Н. Г. Чернышевского, А. И. Герцена, а сочинения M. E. Салтыкова-Щедрина цитировала наизусть целыми страницами.
С ней нужно было держать ухо востро, была она великая насмешница, и Костычеву нередко от нее доставалось. По воспоминаниям одного из знакомых Костычевых, В. Оболенского, Авдотья Николаевна была «одной из образованнейших женщин своего времени» и до самой смерти сохранила «свой живой ум, неподражаемый, чисто щедринский юмор и красочную образность рассказа».
Происходила Авдотья Николаевна из бедной семьи. Отец ее был чиновником XIV класса — это являлось самой низшей ступенью табели о рангах. Костычев и Авдотья Николаевна встречались и на художественных выставках и в публичной библиотеке, на лекциях, а иногда и в Летнем саду или на Островах. В Петербурге было немало хороших мест для встреч и прогулок. Они много и горячо спорили о литературе, о живописи, еще чаще о политике. Постепенно Авдотья Николаевна заражалась интересом своего собеседника к агрономии и естествознанию, поддерживала и подбадривала его в самые тяжелые для него дни, когда он ушел с химического завода или с таким трудом добивался места пробирера.
Как только Костычев получил это место, молодые люди поженились. Их доходы были очень невелики, но они оба не привыкли к роскоши, а труд и лишения их не пугали. Пробирерское жалованье составляло 900 рублей в год, за проведение практических занятий по химии с учениками пробирного училища платили 12 рублей 50 копеек в месяц, кое-что давали литературные заработки, Авдотья Николаевна прирабатывала частными уроками. Так они сводили концы с концами, сняли маленькую и очень скромную квартирку, много работали, иногда ходили в театр, имели обширный круг знакомых. Жили молодожены очень дружно.