Han ægtede [[1868]] Jensine Christine Ørtoft (f. 24. maj 1840), datter af urmager Ørtoft i [[Sæby]].
Hun var gift med en giftspeciel kvindemand der hed [[Ole Veed-fald]] da de mødte hinanden, men ogTutein flyttede sammen med hende til Frederikshavn. Inden ægteskabet fik de to børn. I [[Hørmested sogn]] hvor deres hjem lå fik de yderligere 11 børn. Nummer 4 hed iøvrigt [[Alice Tutein]] og blev senere gift med [[Gustav Wied]]. <ref>"Aneblad" en hjemmeside d.14/6-10 [http://www.gulle.dk/lundholm_arkiv/t/tu/tutein/0002.htm]</ref>
