Die erste Heirat sollte nie zustande kommen, denn der kleine Friedrich starb nur wenige Jahre später. Mathilde und ihre Mutter Eleonore von Aquitanien hingegen bestiegen 1167 in Dover ein Schiff und segelten, begleitet von weiteren Schiffen, die Mathildes Mitgift trugen, zunächst in die Normandie. Von dort reiste die Braut weiter in Richtung Heiliges Römisches Reich. In Minden traf sie auf Heinrich den Löwen, mit dem sie im dortigen Dom am 1. Februar 1168 feierlich vermählt wurde. Mathilde war gerade elf Jahre alt und fast 30 Jahre jünger als ihr Ehemann, der dank ihrer Mitgift zu einem der reichsten Fürsten des Reiches wurde. Für Heinrich war dies die zweite Ehe, nachdem er sich 1162 von seiner ersten Frau Clementia von Zähringen hatte scheiden lassen. 1172 kam das erste Kind, Tochter Richenza, zur Welt, vier weitere überlebten das Kleinkindalter, darunter der spätere Kaiser Otto IV.
