קליבלנד המשיך להתנגד לבזבוז בלתי נחוץ כמושל. הוא הטיל וטו שמונה פעמים בחודשיים הראשונים שלו בתפקיד. הוא הטיל וטו על חוק שנועד להקטין את דמי הנסיעה ברכבת התחתית של ניו יורק לחמישה סנטים. החוק זכה לתמיכה כיוון שהבעלים של הרכבת, ג'יי גולד, לא היה אהוד, ורבים רצו לפגוע באינטרסים שלו. אולם קליבלנד ראה את החוק כלא הוגן - גולד קנה את הרכבת כשהיא הייתה על סף פשיטת רגל והפך אותה לרווחית שוב. קליבלנד גם האמין שהחוק היה בלתי חוקתי. למרות האהדה כלפי החוק, העיתונים שיבחו את קליבלנד על הטלת הווטו. תאודור רוזוולט, שהיה אז חבר באספה הכללית של ניו יורק, תמך בחוק בחוסר רצון למרות התנגדות קליבלנד, כדי לפגוע בבעלי הרכבת. לאחר הטלת הווטו, רוזוולט ומחוקקים אחרים החליטו להתנגד לחוק.
התנגדותו של קליבלנד לשחיתות זיכתה אותו באהדת הציבור, אולם בטינת הטמאני הול בניו יורק סיטי. הטמאני התנגד לקליבלנד כמושל, ולאחר שקליבלנד הכשיל מועמד שלהם מלהיבחר לסנאט, הם החריפו את התנגדותם. קליבלנד גם התנגד למינוי מועמדי הטמאני לתפקידים ולחוקים שהעבירו. למרות חוסר התמיכה מצד הטמאני, רוזוולט ורפובליקנים תומכי רפורמה אחרים תמכו בקליבלנד ועזרו לו להעביר חוקי רפורמה.
בחירות 1884.
המועמדות הדמוקרטית.
הרפובליקנים התכנסו בשיקגו ובחרו ביושב ראש בית הנבחרים, ג'יימס בליין ממיין, כמועמדם לנשיאות בסיבוב הרביעי. רפובליקנים רבים ראו בו אדם תאב כוח ולא מוסרי, ורפובליקנים רבים בשם "Mugwumps" הרגישו נבגדים. המנהיגים במפלגה הדמוקרטית ראו בכך הזדמנות לחזור לבית הלבן לראשונה מאז 1856.
בקרב הדמוקרטים, נחשב סמואל טילדן למועמד המוביל, לאחר היותו המועמד בבחירות של 1876, אולם הוא סירב בשל בריאות לקויה. לאחר שטילדן פרש, עברו תומכיו למועמדים אחרים. קליבלנד זכה לתמיכה, וגם מועמדים כמו תומאס בייארד מדלאוור, אלן תרמן מאוהיו, סמואל מילר מאיווה ובנג'מין באטלר ממסצ'וסטס זכו לתמיכה רחבה. לכל אחד מהם הייתה בעיה: בייארד תמך בפרישה מהאיחוד ב-1861, ולכן לא היה מקובל בקרב הצפוניים. באטלר היה שנוא בדרום בשל פעולותיו במלחמת האזרחים האמריקנית. תרמן היה אהוד, אבל היה מבוגר וחלש, ודעותיו בנוגע להצמדת הדולר לכסף לא היו בטוחות. גם לקליבלנד היו מתנגדים - הטמאני המשיכו להתנגד אליו, אולם ההתנגדות שלהם רק הגבירה את התמיכה בו. קליבלנד הוביל בסיבוב הראשון עם 392 קולות מתוך 820. בסיבוב השני, תמך הטמאני בבאטלר, אולם שאר הצירים החליטו לתמוך בקליבלנד, שניצח. תומאס הנדריקס מאינדיאנה נבחר להיות סגנו.
מסע הבחירות נגד בליין.
השחיתות הייתה הנושא המרכזי במערכת הבחירות של 1884. בליין היה מעורב בנושאים מפוקפקים במהלך הקריירה שלו, וקליבלנד היה ידוע כאדם ישר. הסיסמה שלו הייתה "משרה ציבורית היא אמון ציבורי". הרפובליקנים שתמכו ברפורמה, "Mugwumps", עברו לתמוך בקליבלנד, כיוון שטענו שיוכל לקדם רפורמה בשירות הציבורי ויעילות ממשלתית. הדמוקרטים איבדו תמיכה מצד כמה פועלים לטובת מפלגת השטרות של באטלר, בגלל עמדותיו של קליבלנד. קליבלנד עצמו לא השתתף במסע הבחירות, כנהוג אז, בעוד שבליין כן שבר את המסורת.
מסע הבחירות התמקד באישיותם של שני המועמדים, וכל צד תקף את יריבו. מטה קליבלנד הזכיר את השערוריות שבליין היה מעורב בהן בנושאי חקיקה, טענו שהיה עושה דברם של ארגוני הרכבת, ושהרוויח ממכירת איגרות חוב שהיו לו בארגונים. למרות שהשמועות לא עוררו הדים שמונה שנים קודם לכן, הפעם התגלו יותר ראיות בצורת מכתבים של בליין. בליין הכיר במכתבים ששלח, אולם טען שהם לא מראים שנהג בחוסר הגינות. למרות זאת, תיאורו של בליין כמושחת השפיע על הציבור. במכתבים המפלילים יותר, כתב בליין "שרוף את המכתב", והדמוקרטים הפכו זאת לסיסמה: "בליין, בליין, ג'יימס ג'י. בליין, השקרן ממדינת מיין, שרוף את המכתב!".
רבים טענו שמאז ג'ורג' וושינגטון לא היה מועמד כל כך כנה כמו קליבלנד. אולם הרפובליקנים כן מצאו שלדים בארון של קליבלנד. בעזרת דרשות של כומר מבאפלו, הם חשפו שמועות שלקליבלנד היה בן מחוץ לנישואין בזמנו כעורך דין בבאפלו, ניו יורק, וצעקו "אמא, איפה אבא?". קליבלנד הנחה את תומכיו לספר את האמת. לטענתו, הוא סיפק תמיכה כלכלית לאישה שטענה שהייתה אם ילדו, כיוון שהיה הרווק היחיד מבין האבות הפוטנציאליים. קליבלנד הודה ששילם מזונות החל מ-1874 לאימו של הילד, מריה האלפין. האלפין עצמה קיימה יחסים עם כמה גברים, כולל אוסקר פולסום, ידידו של קליבלנד, שעל שמו נקרא הילד. קליבלנד היה הרווק היחיד מבין האישים שיכלו להיות האב, ולכן לקח אחריות על כך. הדמוקרטים האשימו את בליין ואשתו בכך שלא היו נשואים כשבנם נולד ב-1851. השמועה הייתה לא נכונה ולא השפיעה על מסע הבחירות.
הבחירות היו צמודות במיוחד בניו יורק, ניו ג'רזי, אינדיאנה וקונטיקט. הטמאני הול החליט לתמוך בקליבלנד, כיוון שהיו בטוחים שבכך יוכלו לקבל מינויים פוליטיים מאשר בממשל רפובליקני. בליין קיווה שיזכה לתמיכה מצד הקהילה האירית-אמריקאית יותר מרוב הרפובליקנים. קהילה זו בדרך כלל תמכה בדמוקרטים, אולם אמו של בליין הייתה אירית קתולית, והוא תמך במהלך כהונתו כמזכיר המדינה במאבק האירים. האירים נראו כתומכים בבליין, עד שדובר רפובליקני טען שהדמוקרטים הם מפלגת "רום, רומאיות ומרד". הדמוקרטים הפיצו את העלבון האנטי-קתולי, וטענו שבליין עצמו מנוכר לאירים העניים שכן הוא היה מקושר לעשירים של ניו יורק.
לאחר ספירת הקולות, קליבלנד זכה בכל המדינות המתנדנדות בהפרש צמוד, ובניו יורק בהפרש של 1,200 קולות. הוא זכה להפרש של רבע אחוז בספירת הקולות, אולם השיג 219 אלקטורים לעומת 182 לבליין. לאחר הניצחון, הגיבו הדמוקרטים לצעקות הרפובליקנים: "הלך לבית הלבן, חה חה חה!"
כהונתו הראשונה כנשיא (1885-1889).
קליבלנד כיהן כנשיא מ-4 במרץ 1885 ועד 4 במרץ 1889. הוא כיהן שוב כנשיא בין ה-4 במרץ 1893, וה-4 במרץ 1897. הוא היה הנשיא הראשון מטעם המפלגה הדמוקרטית לאחר מלחמת האזרחים והנשיא היחיד שחזר לאחר הפסד בבחירות לבית הלבן. הוא היה הנשיא ה-22 וה-24.
קליבלנד היה רווק כשנכנס לתפקיד ב-1885, אולם נישא לפרנסס פולסום בבית הלבן ב-2 ביוני 1886. הוא הנשיא היחיד שנישא בבית הלבן.
ממשל וקבינט.
קליבלנד היה צריך להרכיב את הקבינט הדמוקרטי הראשון מאז שנות החמישים, ואף אחד מחברי הקבינט הראשון שלו לא שירתו בקבינט השני שלו. הסנאטור תומאס בייארד, יריבו הגדול במירוץ למועמדות, הסכים לשרת כמזכיר המדינה. דניאל מנינג, יועץ של קליבלנד מניו יורק ובן בריתו של טילדן, הפך למזכיר האוצר. עוד אדם מניו יורק, הבנקאי ויליאם ויטני, מונה למזכיר הצי. לתפקיד מזכיר המלחמה, מונה ויליאם אנדיקוט, שופט ממסצ'וסטס שהיה קשור ל"Mugwumps". קליבלנד בחר גם בשני דרומיים לקבינט שלו: לוציוס למאר ממיסיסיפי כמזכיר הפנים, ואוגוסטוס היל גרלנד מארקנסו לתפקיד התובע הכללי. מזכיר הדואר ויליאם וילאס מוויסקונסין היה המערבי היחיד בקבינט. דניאל לאמונט היה מזכירו האישי של קליבלנד והיה האדם החשוב ביותר בממשל.
רפורמה.
לאחר כניסתו לתפקיד, נאלץ קליבלנד למנות את המינויים שהנשיא היה צריך למנות. המשרות בדרך כלל נתפסו בידי מקורבים פוליטיים, אולם קליבלנד הכריז שלא יפטר רפובליקנים שעושים את עבודתם נאמנה, ושלא ימנה מועמדים על בסיס מפלגתי בלבד. הוא הקטין את מספר העובדים הפדרליים, שהתרבה בזכות המינויים הפוליטיים. הדמוקרטים חפצו בחזרה לשלטון אחרי חצי יובל שנים במדבר הפוליטי, ודרשו מינויים פוליטיים. קליבלנד נאלץ להחליף בעלי תפקידים רפובליקניים בדמוקרטים, אולם קידם בו בזמן את הרפורמה למינוי על פי כישורים.
קליבלנד ניסה ליצור רפורמה בחלקים אחרים של הממשלה. הוא חתם על חוק ב-1887 שיצר ועדה לפיקוח על הסחר הפנימי. בנוסף, פעל ליצירת צי חדשני, וביטל חוזים עם חברות שייצרו ספינות נחותות. קליבלנד הכעיס את המשקיעים במסילות הרכבת כשציווה על חקירה כנגד איגודי הרכבת והאדמות שהחזיקו במערב באישור ממשלתי. לאחר חקירה, נקבע שהאיגודים לא פיתחו את האדמות כראוי, ושהן יחזרו לבעלות ציבורית. כ-330,000 קילומטרים רבועים חזרו לבעלות ציבורית.
קליבלנד גם נלחם להחזיר לנשיא את הסמכות לפטר אנשים ברשות המבצעת ללא אישור הסנאט, זכות שנלקחה בימי הנשיא החלש אנדרו ג'ונסון (1865-1869). קליבלנד הצליח לבטל את החוק ב-1887.
וטו.
קליבלנד נלחם מול סנאט רפובליקני, ונאלץ להפעיל את זכות הוטו שלו. הוא הטיל וטו על מאות חוקים שנועדו לשלם ללוחמי מלחמת האזרחים, כיוון שהאמין שאין לקונגרס זכות לבטל החלטות של משרד הפנסיה. הקונגרס העביר חוק למתן קצבאות, גם לפציעות לא משירות צבאי, וקליבלנד ביטל זאת. הוא הטיל וטו יותר מכל נשיא עד אז. בנוסף, הטיל וטו על חוק שנועד להקציב 10,000 דולרים לצורך רכישת זרעים לחקלאים בטקסס, שבצורת הרסה את יבוליהם. הוא התנגד לכך בטענה שהממשלה צריכה להגביל את עצמה.
הכסף החופשי.
אחת מהשאלות הבוערות של אותה התקופה הייתה האם לגבות את הדולר בזהב ובכסף, או בזהב בלבד. הרפובליקנים המערביים והדמוקרטים הדרומיים דרשו הטבעה חופשית של מטבעות כסף, ונציגים של שתי המפלגות מצפון-מזרח המדינה תמכו בתקן הזהב. הכסף היה שווה פחות מסכום ההמרה שלו בזהב, וכך משלמי המיסים שילמו את חובותיהם בכסף, ואילו מלווים בינלאומיים דרשו תשלום בזהב, כך שמלאי הזהב הלך והידלדל.