Кливленд продолжал юридическую практику, но намерений получить выборную должность не оставлял. Такая возможность возникла, когда в 1870 г. открылась вакансия шерифа того же графства Эри (к этому времени подобные должности стали выборными) — то ли руководителя, то ли сотрудника полицейской службы, в обязанности которого входили поддержание правопорядка, помощь судебным органам в отправлении правосудия, управление местными исправительными заведениями. В различных штатах функции шерифов могли иметь разный объем и характер. В северо-восточных штатах, к которым относился Нью-Йорк, шерифы имели минимальные права — управляли тюрьмой, обеспечивали безопасность судов, вручали повестки в суд. Полиция им не подчинялась.
Несмотря на то что сколько-нибудь больших возможностей эта должность не сулила, Кливленд принял участие в выборах и выиграл их в начале 1871 г. Имея в виду ограниченность его функций и прав, часть биографов считает, что эта работа, продолжавшаяся десять лет (он переизбирался каждые два года), была потерянным временем. Вряд ли с этим можно согласиться. Кливленд накапливал административный опыт, учился работать дисциплинированно, не уклоняясь от самых неприятных акций (он дважды сам приводил в исполнение приговоры о повешении), но в то же время закрывал глаза на случаи взяточничества, когда они были связаны с лицами, с которыми надо было поддерживать нормальные отношения.
В этот период у Кливленда возникла неприятность личного характера, которая была вроде бы преодолена, но позже широко использована оппонентами и чуть было не стоила президентского кресла. Уже не юноша, но еще холостяк, он вступил в связь с некой вдовой по имени Мария Хэлпин, которая забеременела то ли от него (он решительно отрицал сей факт), то ли от кого-то другого. Пытаясь заставить Кливленда жениться, эта дама обвинила его в изнасиловании, в результате которого она родила ребенка. Кливленд убедил судей, что Мария Хэлпин была алкоголичкой и пыталась соблазнить не только его, но и других мужчин, чтобы заставить взять ее в жены. В результате эту даму даже на краткий срок отправили в исправительное заведение. Что же касается крохотного ребенка, то Кливленд, по его словам, решил позаботиться о нем просто из добрых чувств и устроил его в какую-то бездетную семью (вскоре ребенок был возвращен матери). Что было на самом деле, так и осталось неизвестным. Был ли это его ребенок или нет — неведомо. Но когда дотошные журналисты во время избирательной кампании 1884 г. раскопали эту историю, Кливленду и его штабу стоило немало сил и средств, чтобы убедить избирателей, что он был ни при чем.
Пока же Кливленд считался честным и добросовестным чиновником, что в Буффало было редкостью. Не только местная, но и национальная пресса публиковала разоблачительные статьи об администрации города и графства. В этих условиях лидеры местной организации Демократической партии попытались восстановить свою репутацию, выдвинув Кливленда на пост мэра города. На состоявшихся в 1881 г. выборах он получил большинство голосов и в январе 1882 г. вступил в должность. Почти сразу он стал широко известен непримиримостью к коррупционным схемам и административному покровительству бизнесам, связанным с партией, стоявшей у власти. Ему предстояло просто утвердить решение местной легислатуры о контракте на очистку улиц, подписанном с некой фирмой с оплатой из казны свыше 400 тыс. долларов, тогда как другая фирма, не связанная с партийной машиной, предлагала свои услуги с оплатой на 100 тыс. долларов дешевле. Партийные боссы демократов из Буффало были уверены, что их однопартиец послушно одобрит контракт. Но Кливленд отказался это сделать, запретил подписывать документы. Машина Демократической партии вынуждена была не только считаться с этим, но использовала поведение Кливленда в своих целях. Вслед за этим мэр вновь стал известен тем, что лично нашел фирму, которая согласилась за сравнительно небольшую плату (значительно меньшую, чем предлагали другие компании, связанные с партийными штабами) осуществить переоборудование городской канализации.
Все эти неожиданные для нью-йоркской провинции действия создавали Кливленду репутацию неподкупного и эффективного чиновника, отдающего все силы заботе о благе населения. Очень скоро партийные лидеры стали рассматривать его кандидатуру в качестве возможного номинанта на пост губернатора Нью-Йорка. Проработав мэром менее одного года, Кливленд был выдвинут на должность губернатора одного из важнейших и крупнейших штатов. Съезд партийной организации штата номинировал именно его, так как соперничавшие группы никак не могли договориться между собой, а провинциальный и авторитетный мэр не входил ни в одну из фракций.