Urodził się w rodzinie ziemiańskiej we wsi Wola Rafałowska w roku 1807. Kształcił się w gimnazjum w Rzeszowie, następnie we Lwowie. Tam też studiował prawo, ale studiów nie ukończył.
Walczył w powstaniu listopadowym na terenie Królestwa Kongresowego, po upadku powstania próbował przedostać się do Grecji, osiadł w Trieście, a następnie w Padwie, gdzie kontynuował studia. Z tytułem doktora obojga praw powrócił do Lwowa, odbył praktykę adwokacką, a w 1839 roku przybył do Tarnowa i otworzył tutaj kancelarię adwokacką.
Podczas rabacji w 1846 roku przebywał w Tarnowie, podczas Wiosny Ludów, w 1848 roku, Klemens Rutowski doprowadził do postania w Tarnowie Obwodowej Rady Narodowej, prowadził też zapisy do Gwardii Narodowej, której był kapitanem. W efekcie po upadku rewolucji objęty został policyjnym nadzorem.
Do polityki powrócił w roku 1861, kiedy to został posłem z Tarnowa do Sejmu Krajowego we Lwowie. Po wybuchu powstania styczniowego Klemens Rutowski kierował organizacją narodową obwodu tarnowskiego, działał również jako łącznik pomiędzy konspiratorami tarnowskimi i krakowskimi. Żona - Karolina Rutowska - należała do tarnowskiego oddziału Komitetu Niewiast Polskich, zajmującego się opieką nad rannymi powstańcami przybywającymi do Tamowa.
Mimo, iż był posłem do Sejmu Krajowego Klemens Rutowski został w 1864 roku aresztowany. Represje wykreowały go na męczennika sprawy narodowej. W marcu 1867 roku został wybrany do Rady Miasta Tarnowa, był także zastępcą pierwszego autonomicznego burmistrza Tarnowa - Wojciecha Bandrowskiego. W kolejnej kadencji, w roku 1870, sam był zainteresowany stanowiskiem burmistrza, a kiedy rajcy wybrali ponownie Bandrowskiego, zrezygnował ze stanowiska wiceburmistrza. W 1870 roku Rutowski uzyskał ponownie mandat poselski z Tarnowa do Sejmu Krajowego, a trzy lata później, po wyborach w roku 1873 objął wreszcie 28 grudnia stanowisko burmistrza miasta, popierany przez 24 rajców.
W następnym roku ukończono budowę szkoły przy ulicy Kopernika, rozpoczętą za kadencji poprzednika. Dzięki tej inwestycji przeniesiono do Tamowa z Nowego Sącza Seminarium Nauczycielskie, które zlokalizowano na drugim piętrze nowego budynku szkoły.
Samorząd Tarnowa cały czas borykał się jednak z brakiem funduszy i deficytem budżetowym. Mimo zaciągania kolejnych pożyczek niedobór w budżecie gminy się powiększał, podatków w obawie przed porażką wyborczą nie zdecydowano się podwyższyć, burmistrzowi zarzucano natomiast, że interesuje się bardziej administrowaniem swoimi majątkami ziemskimi i praktyką adwokacką, niż sprawami Tarnowa.
W obliczu niemalże krachu finansowego gminy Namiestnictwo we Lwowie 24 marca 1877 roku rozwiązało Radę Miejską w Tarnowie i zaprowadziło Tymczasowy Zarząd Komisaryczny. Był to jedyny tego typu wypadek w mieście w czasach austriackich, czyli do roku 1918. Komisarzem rządowym na okres od 4 kwietnia do 29 listopada 1877 roku został Władysław Krzaczkiewicz. Po tej politycznej porażce Klemens Rutowski zaczął wycofywać się z życia publicznego, choć do śmierci prowadził w Tarnowie swoją kancelarię adwokacką.
Zmarł 24 stycznia 1896 roku w wieku 89 lat, jego syn Tadeusz Klemens Rutowski (1852-1918) był również znanym politykiem galicyjskim, wiceprezydentem Lwowa w latach 1905 - 1918.
