W 1853 tymczasowo zarządzał parafią w Jonkowie, od 1854 był administratorem parafii Lesiny Wielkie na Mazurach. Jako proboszcz misyjny działalność duszpasterską prowadził też w pobliskich Klonie, Zieleńcu, Lipowcu, Wielbarku, Szczytnie. Inicjował zakładanie szkół i cmentarzy, a w samych Lesinach zaangażował się w budowę plebanii i szkoły. W 1856 powrócił do pracy duszpasterskiej na Warmii, obejmując probostwo w Barczewku. Nie zerwał jednak więzów z parafiami mazurskimi, gromadził środki finansowe na budowę obiektów sakralnych (wspomagał je także własnymi oszczędnościami); ufundował dzwon do kościoła w Lesinach, nazwany na jego cześć "Valentinusem". Od 1869 ponownie działał w Olsztynie.
Aktywną działalność ks. Tolsdorf wykazywał na polu walki z alkoholizmem. W 1846 w Olsztynie powołał do życia Towarzystwo Wstrzemięźliwości (Enthaltsamkeits-Verein), ukierunkowane przede wszystkim na warstwy robotnicze. Powstanie Towarzystwa ogłosił na uroczystej mszy w kościele św. Jakuba we wrześniu 1846, głosząc kazanie po niemiecku i po polsku. Odebrał wówczas przysięgę od 28 członków założycieli;