Германии на Русь не явилось свадебное посольство от саксонского дома Штаденов. Отец Евпраксии, заинтересованный в родстве со знатным германским семейством, дал согласие. По тогдашнему обычаю, её рано выдали замуж: в 12 лет. Девочка была отправлена в Саксонию в жёны к немолодому Генриху Штаденскому вместе с «несметным богатством, нагруженным на верблюжий караван».
Прибывшие повозки с приданым передали жениху, Генриху Штадену, а саму Евпраксию отдали на воспитание и обучение в Кведлинбургский женский монастырь, где она должна была научиться говорить по-немецки, читать на латыни (который был официальным языком Европы того времени). Её греческое имя — Евпраксис («добродеяние») заменили католическим аналогом — Пракседис. За три года, проведённых в монастыре под надзором сестры императора, двадцатипятилетней Адельгейды, Евпраксия овладела не только языками, но и «книжными премудростями». В 15 лет она приняла католичество и получила при крещении новое имя Адельгейда — имя своей главной воспитательницы.
Вскоре состоялось и её обручение с Генрихом Штаденом, но брак оказался недолгим: менее, чем через год Генрих при невыясненных обстоятельствах умер (1087). Маркграфство перешло по наследству к брату умершего, Людигеру. А бездетная юная вдова, Евпраксия-Адельгейда, вновь вернулась в Кведлинбургский монастырь к аббатисе и воспитательнице.
Здесь на близком знакомстве с пятнадцатилетней русской вдовой настоял брат аббатисы — германский император Генрих IV, по странной случайности сам 27 декабря 1087 года потерявший жену Берту и ставший вдовцом.
Русской княжне он показался весьма привлекательным, особенно после четырёх лет однообразной, монотонно-скучной жизни в монастыре. Прельщённый юностью и воспитанностью Евпраксии, сильно отличавшейся умом и красотой от его придворных дам, как утверждал один из немецких хронистов, Генрих IV возложил надежды на установление через неё родства с могущественным киевским княжеским домом. Император хотел привлечь Русь в союзники в борьбе с римским папой, Урбаном II, и могущественной маркграфиней тосканской Матильдой.
В 1088 году Генрих IV сделал Евпраксии предложение стать германской королевой. Киевский князь послал дочери своё благословение. 14 августа 1089 года было официально объявлено о коронации. В Киев было послано извещение о браке и выражена надежда на взаимопонимание. Однако цель не была достигнута: Византия прервала взаимоотношения с Германией, а византийский император Иоанн II Продром, стремившийся удержать Русь в сфере своей политики, дал понять, что новый брак Евпраксии не поддерживает. Киев отказался вступать в союз с Генрихом IV.
Юная королева оказалась в непростом положении. Став в 19 лет соправительницей громадной Священной Римской империи, она не имела возможности не только решать что-либо самостоятельно, но даже узнать о родных, о сёстрах, оставшихся в Киеве. Да и новый муж, как выяснилось, имел «необузданный характер»: с ним не ужились ни мать Агнесса, ушедшая от сына, едва он стал совершеннолетним, в монастырь, ни выросшие сыновья от первого брака. Хронисты сообщают (возможно, преувеличивая), что Генрих IV принадлежал к секте сатанистов-николаитов, тайные мессы которой сопровождались развратными действиями.
О безнравственности германского императора многим было известно задолго до его брака с Евпраксией. Жестокие издевательства Генриха IV над первой женой и сестрой («которую он своими руками держал в то время, когда другой её насиловал») дважды обсуждались на княжеских съездах 1073 года в Корбее и в Герстунгене. Немецкие хронисты Бруно и Ламберт оставили описания кровосмесительных отношений Генриха IV с его сестрой Адельгейдой (той самой, что воспитывала Евпраксию).
Охлаждение между супругами наступило быстро. После того как в 1089 стало ясно, что планам Генриха IV по вовлечению Киева в продолжавшуюся борьбу с папским престолом не суждено сбыться, император начал вымещать свою злобу на жене. Их отношения стремительно принимали скандальные формы. Вот что сообщают под 1093 годом «Анналы пастыря св. Дисибода» (источник 40-х годов XII века, отразивший не дошедший в самостоятельном виде источник, описывающий историю разрыва между Генрихом и Евпраксией):
«Конрад, сын императора Генриха (от первого брака. — С. Ц.) восстал против своего отца по следующей причине. Король Генрих возненавидел королеву Адельхайду, свою жену, да так, что ненависть была ещё сильнее, чем страсть, с какой он её прежде любил. Он подверг её заключению и с его позволения многие совершали над ней насилия. Как говорят, он впал в такое безумие, что даже упомянутого своего сына убеждал войти к ней. Так как тот отказался осквернить ложе отца, король, уговаривая его, принялся утверждать, будто он не его сын, а одного чужака, швабского герцога, на которого названный Конрад был чрезвычайно похож лицом. Королева же, после множества неслыханных оскорблений, нанесённых ей без вины, каким-то образом по милости Божией освободившись бегством из заключения, в котором находилась, прибыла к могущественнейшей в то время госпоже по имени Матильда (герцогине Тосканской, одной из наиболее решительных сторонниц папы. — С. Ц.). Приняв королеву, она сопроводила её к досточтимому мужу Урбану, занимавшему [тогда] апостольский престол (папе Урбану II, 1088–1099. — С. Ц.). Припав к его ногам, обливаясь слезами, в сердечном сокрушении она жаловалась о всех бедах и несчастиях, которые перенесла. Господин же папа, узнав о бедствиях королевы, движимый милосердием и состраданием, собрал всеобщий собор, который снова (Генрих уже подвергался однажды отлучению при Григории VII. — С. Ц.) отлучил короля Генриха от церкви за недопустимые, безбожные и вовеки неслыханные дела, совершённые над собственной законной супругой. Королева же, как утверждают некоторые, вернулась в свою страну и, уйдя в монастырь, стала аббатисой».
Более детальные сведения о судьбе Евпраксии Всеволодовны в Италии обнаруживаем в современной «Хронике» Бернольда (ум. в 1100), монаха в швабских монастырях св. Власия в Шварцвальде, а затем в Шафхаузене, последовательного сторонника папы:
«Супруга императора, уже в течение долгого времени жертва множества беззаконий, много лет содержавшаяся под стражей, дабы не скрылась, в конце концов бежала к итальянскому герцогу Вельфу (мужу Матильды Тосканской. — С. Ц.). Она поведала, что претерпела… столь великие и столь неслыханные злодейства, что не сомневалась — даже у недругов она найдёт сострадание… Эта надежда её не обманула, ибо герцог и его супруга Матильда приняли её милостиво и относились к ней с почтением».
В начале апреля в швабском городе Констанце по инициативе местного епископа собрался церковный собор.
«До Констанцского собора дошла жалоба королевы Пракседы, которая давно скрылась от своего мужа у Вельфа, герцога Италии, и сетовала на столь многочисленные и столь неслыханные и грязные блудодеяния, перенесённые ею от столь многих, что даже враги её легко простили бы ей её бегство, и все собравшиеся на синод были подвигнуты состраданием к ней».
В марте следующего, 1095 года в городе Пьяченца (в Ломбардии
