Со студенткой Академии экономики и финансов Ольгой Шадриной Павла Руденко познакомил дядя девушки – санитар онкологического диспансера Подгорный весной 1997 года (сам Подгорный был знаком Руденко по совместным занятиям в спортзале). Студентка из шахтерского сибирского города Прокопьевска пленила сердце молодого прокурорского работника. Молодые люди стали регулярно встречаться, ходить в театры и на концерты в филармонию. Руденко так увлекся девушкой, что уже всерьез считал ее своей невестой. Он разрешил ей жить в квартире, оставшейся ему от бабушки (сам помощник прокурора жил с родителями в другом месте). Шадрина должна была оплачивать квартплату, коммунальные услуги и телефон.
А вот сама Шадрина надежды на будущее только с Руденко не связывала. В конце 1997 года в Петербург из Прокопьевска приехала мать Ольги, чтобы купить дочери здесь квартиру. Надежды Павла Руденко на счастливое будущее были столь велики, что он, невзирая на неудовольствие собственных родителей, встретил в компании с дочерью и матерью Шадриными новый, 1998 год. Чуть позже, весной, мать за 32,5 тысячи долларов купила Ольге квартиру на площади Чернышевского. Часть денег – 800 долларов – ей пришлось одолжить у Руденко. В залог возвращения денег мать Шадриной передала Руденко два золотых кольца с бриллиантами и пообещала вернуть деньги с процентами.
И в этот момент отношения между молодыми людьми стали стремительно портиться. Павел Руденко стал все активнее говорить с Ольгой о предстоящей свадьбе. Она же принимала ухаживания помощника прокурора со все убывающим энтузиазмом. С квартиры, которой девушка пользовалась с любезного разрешения Руденко, она съехала и перебралась в студенческое общежитие. В мае 1998 между ними состоялось очередное бурное объяснение, на котором Шадрина вернула молодому человеку ключи от бабушкиной квартиры, сообщила о покупке собственного жилья и заявила, что замуж за Руденко вовсе не собирается.
По словам Шадриной, Руденко вспылил и пригрозил, что в таком случае она «никому не достанется, а отправится навечно «плавать» в один из городских водоемов». Сам Руденко, впрочем, утверждал, что все это наговоры, и именно девушка хотела выйти за него замуж и не возвращать таким образом долг матери, а он не был согласен, поскольку деньги принадлежали его родителям, да и жениться на Шадриной он к тому времени раздумал.
Как бы то ни было, расстались они после того, как помощник прокурора напомнил своей «невесте» про 800 долларов и потребовал вернуть долг в течение недели. Денег Шадрина не отдала и начала скрываться от «навязчивого жениха». К середине июня 1998 года Руденко обозлился настолько, что перешел к решительным действиям. Разузнав в институте новый адрес девушки, он заявился к ней «в гости» и стал намекать, что «за долги квартиру придется переоформить на его людей». Помощник прокурора советовал любимой не перечить ему – в противном случае, мол, в институте про нее станет известно, что Шадрина находится в федеральном розыске за оптовый сбыт наркотиков (позже он осуществил эту угрозу), да и с ней самой могут случиться разные неприятности.
После этого Шадрина написала заявление в прокуратуру, требуя унять «зарвавшегося прокурорского работника». Была проведена проверка, апофеозом которой стала очная ставка недавних «жениха и невесты» в управлении по кадрам городской прокуратуры. На тот момент каких-либо нарушений в действиях Руденко прокуратура не обнаружила.
Он же устроил за «невестой» форменную охоту. В купленной квартире девушка жить не рисковала. В общежитии тоже не появлялась, переехав на время к своему дяде. Поняв, что прокурорская проверка не приносит результата, девушка обратилась в РУБОП, представив в качестве доказательств записи своих телефонных разговоров с Руденко, в которых тот требовал уже якобы 8 тысяч долларов, угрожая в противном случае оставить ее мать без дочери. Правда, эти факты подтверждения в суде не нашли.