Grover Cleveland swoją przygodę z polityką rozpoczął od udziału w wyborach na stanowisko szeryfa w nowojorskim hrabstwie Erie. Erudycją nie porywał tłumów, ale wzbudzał respekt wyglądem. Będąc stałym bywalcem Schenkelberger's Restaurant, gdzie regularnie jadał kiełbaski popijane piwem, szybko przybrał na wadze. W drugiej połowie XIX wieku stateczny i elegancki kawaler z nadwagą mógł wzbudzać jedynie szacunek i uznanie. Taki wygląd wskazywał na zamożność, umiejętność poradzenia sobie z przeciwnościami losu i siłę. Dlatego bez większych problemów Cleveland wygrał wybory na szeryfa hrabstwa Erie. Ta posada zapewniała mu stały dochód i przepustkę na nowojorskie salony. Z powierzonych obowiązków wywiązywał się z wielką skrupulatnością. Nawet egzekucje więźniów wykonywał osobiście. Zakładanie stryczka na głowy skazańców w żaden sposób nie burzyło w nim spokoju ducha. Był dżentelmenem, który zgodnie z wiktoriańskim kodeksem towarzyskim łączył w sobie grzeczność i łagodność wobec pań ze stanowczością i gorliwością w walce z przestępczością. W epoce powszechnej korupcji Cleveland wyróżniał się nieskazitelną uczciwością. I to prawdopodobnie ta cecha najbardziej zwróciła uwagę śmietanki politycznej Buffalo, która zachęcała go do ubiegania się o urząd burmistrza tego miasta.
Cleveland przyjął propozycję i mimo niewielkiego budżetu na kampanię wygrał wybory bez zawierania jakichkolwiek kompromisów politycznych i w 1882 r. został zaprzysiężony na burmistrza Buffalo. Teraz miał okazję pokazać swoje talenty organizatorskie na szerszą skalę. Dzięki odrzuceniu nieuczciwych kontraktów publicznych zawartych przez jego skorumpowanego poprzednika zaledwie w ciągu roku zmniejszył deficyt budżetowy, oszczędzając w kasie miejskiej milion dolarów. Rozpoczął też śledztwo, które ujawniło w ratuszu malwersacje na niesłychaną skalę. Aresztowanie skorumpowanych urzędników przyniosło mu olbrzymią popularność wśród mieszkańców miasta.
Cleveland wyróżniał się nieskazitelną uczciwością na tle całego kraju. Początkowo był związany ze środowiskiem republikańskim. Jednak jego krytyka różnych grup interesów powiązanych z tą partią spowodowała, że już po roku od wyboru na urząd burmistrza stał się największym wrogiem tej formacji. Tę sytuację natychmiast wykorzystali demokraci, którzy zaproponowali mu, by reprezentował ich partię w wyborach na gubernatora stanu Nowy Jork. Początkowo Cleveland się wahał. Od wielu dekad mieszkańcy stanu tradycyjnie głosowali na republikanów kojarzonych jako środowisko polityczne, które obroniło Unię w wojnie secesyjnej. Dopiero deklaracja poparcia ze strony wpływowego dziennikarza i wydawcy Daniela Manninga, który w przyszłości zostanie sekretarzem skarbu, przekonała Clevelanda, że ma szansę wygrać wybory na gubernatora. Mimo że republikanie wystawili do wyborów Charlesa J. Folgera, którego osobiście wspierał prezydent Chester A. Arthur, uczciwy burmistrz Buffalo wygrał w cuglach.
Błyskawiczna kariera burmistrza Buffalo
1 stycznia 1883 r. Grover Cleveland objął obowiązki gubernatora stanu Nowy Jork. Wydawało się, że podobnie jak w Buffalo wymiecie skorumpowanych urzędników z Albany (stolicy stanu Nowy Jork). Nadal wykonywał swoje obowiązki z ogromną skrupulatnością i uczciwością, jednak wyraźnie uległ wpływom lobby finansowego najbogatszego wówczas stanu w Ameryce. Nie cieszył się już takim poparciem wyborców jak w Buffalo. Jego popularność spadła, zwłaszcza wtedy, gdy zawetował ustawę obniżającą cenę biletu kolejki naziemnej z 10 do 5 centów. W prasie pojawiły się sugestie, że „uczciwy" gubernator został przekupiony przez właściciela kolejki Jaya Goulda. Dowodem na to miał być list Goulda do gubernatora, w którym przedsiębiorca napisał: „Myślę, że ludzie biznesu w naszym kraju mogą się czuć bezpieczni pod pańskim przywództwem". Znany publicysta i rektor Cornell University Andrew Dickson White stwierdził, że kamień spadł mu z serca, bo gubernator Cleveland porzucił swoje wcześniejsze „sympatie dla robotników" i stanął po stronie przedsiębiorców.
Była to opinia krzywdząca. Cleveland wcale nie był takim figurantem i popychadłem wielkiego biznesu, jak chcieli to widzieć republikanie. O tym, że potrafił się sprzeciwić naciskom ze strony establishmentu, świadczy fakt, że odmówił Johnowi Kelly'emu, potężnemu przewodniczącemu Partii Demokratycznej w Nowym Jorku, mianowania na wysokie stanowiska w administracji stanowej niekompetentnych aktywistów tej partii. W Tammany Hall, siedzibie demokratów, zaczęto z niepokojem dyskutować o lojalności Clevelanda. Stronnicy Kelly'ego głośno krytykowali gubernatora, ostrzegając swoich kolegów z innych stanów, że może on stanowić zagrożenie dla interesów partii.