Краснодарского крайкома хотел, чтобы вверенный ему регион был лучшим везде и во всем. Тем подчиненным, которые могли обеспечить высокие показатели, он был готов простить все. И предприимчивые товарищи этим пользовались. Ходили слухи, что Медунова ждет карьера в Москве, пост союзного министра сельского хозяйства. Но вместо этого началось расследование, в сети которого попадалось все больше и больше людей, так или иначе связанных с главой крайкома партии.
В 1973–1982 годах – 1-й секретарь Краснодарского крайкома КПСС. В 1976–1983 годах – член ЦК КПСС. Был другом Брежнева. По свидетельству И. К. Полозкова, после смерти секретаря ЦК по селу Фёдора Кулакова в 1978 году, на этот пост рассматривалась кандидатура Медунова, но тот отказался.
В 1982–1983 годах в рамках проводимой тогда Ю. В. Андроповым чистки партийных органов, был снят с должности 1-го секретаря крайкома партии, затем выведен из состава ЦК КПСС (с убийственной тогда для номенклатурного работника его уровня формулировкой: «За допущенные ошибки в работе») после предъявления ему обвинений в коррупции в связи с Сочинско-краснодарским делом, которые впоследствии были с него сняты.
Инициатором расследования криминальной ситуации, сложившейся в Краснодарском крае при первом секретаре Сергее Медунове, выступил председатель КГБ Ю. Андропов. При расследовании Следственной частью Прокуратуры СССР дела по Министерству рыбного хозяйства СССР («Рыбное дело»), где проходили многие чиновники, занимавшие высокие должности, следователи вышли на курортный город Сочи.
Там их заинтересовал директор первого тогда в стране магазина фирмы «Океан» Пруидзе, который был арестован за передачу взятки заместителю министра В. И. Рытову. Затем последовали аресты и других сочинских чиновников: заместителей директора магазина «Океан», директора базы Мясорыбторга, начальника гаража совминовского санатория и ещё нескольких человек. В показаниях появилась фамилия председателя Сочинского горисполкома Воронкова. Так возникло непосредственно уже «Сочинско-краснодарское дело». Оно состояло из ряда отдельных дел, которые следователи направляли в суд по мере их окончания, объединённых лишь своей принадлежностью к этому краю.
Вскоре после того, как председатель Сочинского горисполкома Воронков попал в орбиту следствия, он был арестован и препровождён в Лефортовскую тюрьму. Вспоминая это дело, старший следователь по особо важным делам при Генеральном прокуроре СССР Владимир Иванович Калиниченко рассказывал:
«В Сочи началась паника. В ход пошли широко известные приёмы коррумпированных группировок. Они пытались доказать, что показания обвиняемых о взяточничестве серьёзного внимания не заслуживают, что дают их люди, «длительное время содержавшиеся под стражей и находящиеся в условиях изоляции». Именно эту фразу будет позже обыгрывать Медунов в публичных выступлениях, на страницах печати, в докладных записках в ЦК КПСС».
В ходе расследования этого дела более 5000 чиновников были уволены со своих постов и исключены из рядов КПСС, примерно 1500 человек осуждены и получили