Życiorys Otto pochodził z rodziny szlacheckiej, był synem barona Müsselbach lub Mistelbach. Wg Stanisława Rosika rodzicamiprzypis #3 do Świętego Ottona z Bambergu żywot z Prüfenig Ottona byli Otton (ok. 1040–ok. 1070) i Adelajda (1045–1094) prawdopodobnie ze Staufów, a jego bratemprzypis #211 do Żywot Świętego Ottona z Bambergu Ebona – Fryderyk z Mistelbach (zm. ok. 1136)przypis #146 do Świętego Ottona z Bambergu żywot z Prüfenig. Został wychowany w klasztornej szkole z przeznaczeniem do stanu duchownego.
Około 1080 przybył do Polski jako kleryk, towarzysząc opatowi Henrykowi z Wülzburga, który niedługo potem został arcybiskupem gnieźnieńskim. W Gnieźnie Otton prowadził chłopięcą szkołę katedralną i zdobył zaufanie księcia. W 1088 znalazł się na dworze księcia Władysława Hermana w Płocku, gdzie brał udział w pertraktacjach dotyczących małżeństwa księcia z księżniczką Judytą Salicką, siostrą cesarza Henryka IV. Ten rozpoznał w nim lojalnego, mądrego i pobożnego doradcę, wciągając go do swojego otoczenia, gdzie doszedł do rangi kanclerza i strażnika pieczęci. Po ślubie Otton został mianowany również dworskim kapelanem księżnej Judyty.