Przyjechał do Warszawy i rozpoczął urzędowanie 1 grudnia 1875.
Po zapoznaniu się z sytuacją w swoim nowym miejscu pracy za najpilniejszą uznał poprawę stanu higieny w mieście i zdrowotności jego mieszkańców. Jego największą zasługą było zbudowanie w kolejnych latach miejskiego systemu wodno-kanalizacyjnego ze Stacją Filtrów na Koszykach, dokąd ze Stacji Pomp Rzecznych na Czerniakowie doprowadzono wodę czerpaną z Wisły.
Dzięki swojej energii i umiejętności przekonywania przezwyciężył biurokratyczne przeszkody w Petersburgu dotyczące finansowania tego wielkiego projektu, a także krytykę jego licznych polskich przeciwników (m.in. właścicieli warszawskich kamienic). Przesłanie przez Starynkiewicza szczegółów planowanych rozwiązań wodno-kanalizacyjnych do prasy wywołało bowiem medialną burzę. Odpowiadając na głosy krytyczne opublikował on wtedy kilkanaście artykułów polemicznych, przekonywał swoich adwersarzy w bezpośrednich rozmowach, a w 1880 zorganizował trzy publiczne spotkania z kierownikiem prac Williamem Heerleinem Lindleyem, w czasie których wyjaśniono wiele kwestii spornych. W 1881, po zaakceptowaniu projektu przez cara Aleksandra III, Starynkiewicz powołał Komitet Budowy Kanalizacji i Wodociągów m. Warszawy (nazywany zwyczajowo Komitetem Kanalizacyjnym) i sam stanął na jego czele.