ב-1958, ניסה וולאס להתמודד בבחירות המקדימות במפלגה הדמוקרטית לתפקיד המושל. מאז שהחוקה ב-1901 שללה זכות הצבעה משחורים, ומרוב הלבנים העניים, הייתה המפלגה הדמוקרטית המפלגה היחידה באלבמה. הבחירות המקדימות היו התחרות היחידה על תפקיד המושל. הייתה זאת צומת דרכים עבור וולאס. יריבו היה התובע הכללי של המדינה, ג'ון מלקולם פטרסון, שהיה ליברל. וולאס זכה לתמיכת ה-NAACP. הוא הפסיד בבחירות בהפרש של יותר מ-34,400 קולות.
לאחר מערכת הבחירות, החליט וולאס לאמץ קו נוקשה בנושאים גזעיים ולמשוך את הקולות הלבנים לקראת מערכת הבחירות ב-1962.
מושל אלבמה.
הפרדה גזעית.
בבחירות המקדימות של המפלגה ב-1962, הצליח וולאס להגיע למקום הראשון עם 35% מהקולות. בסיבוב השני, השיג 55% מהקולות. כיוון שאף רפובליקני לא התמודד מולו, היה ברור שוולאס ייבחר לתפקיד המושל. הוא נבחר בקלות בבחירות של נובמבר, כשהוא משיג 96% מהקולות. השלטון הדמוקרטי באזור הושג בעזרת ביטול זכות ההצבעה של רוב השחורים ולבנים עניים רבים במדינה במשך עשור, שנמשך גם שנים לאחר העברת חוקי זכויות האזרח ב-1964 וב-1965.
וולאס נשבע אמונים ב-14 בינואר 1963, באותו מקום בו כמעט מאה ושתיים שנים קודם לכן, הושבע ג'פרסון דייוויס לתפקיד נשיא קונפדרציית המדינות של אמריקה. בנאום ההשבעה שלו אמר וולאס: המשפט נכתב בידי כותב הנאומים החדש שלו.
ב-1963, ציווה ממשלו של הנשיא ג'ון פיצג'רלד קנדי על חיל הרגלים של צבא ארצות הברית לאכוף את השילוב הגזעי באוניברסיטת אלבמה. בניסיון למנוע את הרשמת התלמידים השחורים לאוניברסיטה, עמד וולאס לפני כניסת האוניברסיטה ב-11 ביוני 1963. התמונה בה צולם הפכה למפורסמת.
בספטמבר 1963, ניסה וולאס למנוע מארבעה תלמידים שחורים להירשם לארבעה בתי ספר יסודיים. לאחר התערבות מצד בית משפט פדרלי, הורשו הילדים להירשם לבית הספר ב-9 בספטמבר.
וולאס דרש שמירה על ההפרדה הגזעית. הוא האשים את הנשיא קנדי ברצון לוותר על המדינה למרטין לותר קינג ולתומכיו ה"קומוניסטים" שאותם האשים בארגון הפגנות.
וולאס חזה שתומכי חוק זכויות האזרח יחוסלו מבחינה פוליטית עד 1966 ו-1968.
וולאס נחשב לפופוליסט שניסה למשוך את הרוב הלבן בבוחרי אלבמה. כישלונו בהתמודדות על הנשיאות הוביל להפקת לקחים מצד ג'ימי קרטר ורונלד רייגן. ב-1971 הושווה לוויליאם ג'נינגס ברייאן כשנאם נאומים נגד ריכוז העושר.
כלכלה וחינוך.
ההישג המרכזי של וולאס בכהונתו הראשונה היה חידוש הפיתוח התעשייתי באלבמה, שהועתק אחר כך בידי מדינות אחרות: הוא היה המושל הדרומי הראשון שנסע למשרדי תאגידים במדינות הצפון כדי להציע הטבות מס ותמריצים לתאגידים שיקימו סניפים באלבמה.
הוא הנהיג מערכת מכללות שהתפשטה ברחבי המדינה.
אוניברסיטת דרום אלבמה הוקמה ב-1963, במהלך שנתו הראשונה בתפקיד.
הבחירות המקדימות של 1964.
ב-15 בנובמבר 1963, בדאלאס, טקסס, הודיע וולאס על כוונתו להתמודד מול הנשיא המכהן, ג'ון קנדי, בבחירות על מועמדות המפלגה הדמוקרטית לנשיאות ב-1964. כעבור כמה ימים בדאלאס, נרצח קנדי, וסגן הנשיא לינדון ג'ונסון ירש אותו.
בגלל תשומת הלב שזכה לה במאבקו מול זכויות האזרח, נכנס וולאס לבחירות המקדימות של המפלגה בעצת מומחה ליחסי ציבור. הוא הביע את התנגדותו לשילוב גזעי ואת מדיניותו הקשה מול הפשיעה. וולאס השיג לפחות שליש מהקולות בוויסקונסין, אינדיאנה ובמרילנד, בהן התמודד מול נציגי ג'ונסון.
וולאס נודע בנאומיו המתסיסים. ב-1964 נאם בפני אלף אנשים באוהיו, וצעק בכעס שישנם קומוניסטים שמוחים על ביקורו, אולם טען שכשתומכיו יתחילו לצעוד, כל כביש במדינה ייחסם. הקהל קפץ על רגליו ומיהר לצאת לתקוף את הקומוניסטים, כשוולאס ניסה להרגיע אותם.
וולאס קיבל תואר דוקטור לשם כבוד באביב 1964 מאוניברסיטה בקרוליינה הדרומית. האוניברסיטה הוקירה את פועלו בטענה שהוא שומר על זכויותיה החוקתיות של האזרחים.
אלקטור עצמאי ב-1964.
ב-1964, הרוויחו הרפובליקנים באלבמה משתי התפתחויות: הראשונה, הייתה פרישתו של וולאס מהמירוץ מול ג'ונסון, והשנייה הייתה התמודדות אלקטורים דמוקרטים עצמאיים באלבמה, כך שג'ונסון לא יכול היה להתמודד שם. לפני הוועידה הרפובליקנית הלאומית בסן פרנסיסקו, נפגשו וולאס ועוזריו במלון ג'פרסון דייוויס במונטגומרי. וולאס ועוזריו דנו באפשרות שבארי גולדווטר, הסנאטור מאריזונה שעמד להתמנות למועמד הרפובליקנים, והצביע נגד חוק זכויות האזרח מסיבות חוקתיות, יתמוך בביטול החוק ובמתן תעסוקה נאותה לשחורים. וולאס אמנם הסכים עם עמדותיו של גולדווטר נגד הקומוניזם, אולם התנגד לרצונו להפוך את הביטוח הלאומי לתוכנית וולונטרית. וולאס הציע להחליף מפלגות כדי להפוך לסגנו של גולדווטר, כבוד שניתן לאחר מכן לחבר הקונגרס ויליאם אדוארד מילר מניו יורק. גולדווטר סירב למועמדותו של וולאס בגלל שכוחו היה רק בדרום.
האלקטורים העצמאיים מאלבמה הוציאו את ג'ונסון מהבחירות באלבמה אולם עדיין זכו לתמיכת המפלגה בגלל התמודדותם מול הרפובליקנים.
האלקטורים הרפובליקנים של 1964 היו הראשונים שנבחרו באלבמה מאז תקופת השיקום. גולדווטר ומילר זכו ל-479,085 קולות (69.5%) לעומת 209,848 (30.5%) לאלקטורים העצמאיים. בנוסף, נבחרו חמישה חברי קונגרס רפובליקנים. הסנאטור החדש ג'יימס מרטין לטש עיניים לתפקיד המושל של וולאס.
הג'נטלמן הראשון של אלבמה.
חוקת אלבמה מנעה מוולאס להתמודד לכהונה שנייה ב-1966. לכן הציע וולאס לאשתו, לורלין, להתמודד על תפקיד המושלת מטעמו. בבחירות במפלגה הדמוקרטית, היא ניצחה שני מושלים לשעבר, את התובע הכללי של אלבמה ואת חבר הקונגרס לשעבר. בגלל תומכי וולאס, שונתה ההגבלה על כהונת המושל באלבמה לשתי כהונות רצופות.
וולאס הגן על מועמדותה של אשתו. הוא טען שאשתו משכה קהל והתעלמה מהעלבונות שהופנו כלפיה. הוא טען שלא הכניס את אשתו לתפקיד, ושהיא אהבה את הכהונה שלה.
במהלך מערכת הבחירות של 1966, חתם וולאס על חוק שביטל את פקודות ביטול ההפרדה הגזעית בערים ובמוסדות הממשלה. הוא טען שהחוק מנע מהממשלה להתערב בבתי הספר. רבים גינו אותו על כך וחששו מאובדן התמיכה הממשלתית. המועמד הרפובליקני לתפקיד המושל האשים את הדמוקרטים במשחק פוליטיקה על חשבון ילדי המדינה.
גם המועמד הרפובליקני התנגד לביטול ההפרדה הגזעית וניסה לתמוך בתיקון לחוקה שיאסור על העדפה מתקנת בחינוך. הוא חזה שהחקיקה של וולאס לגרום לצו מבית המשפט להוביל לביטול ההפרדה הגזעית.
לורלין וולאס ניצחה בבחירות ב-8 בנובמבר 1966. היא הושבעה בינואר 1967, אולם ב-7 במאי 1968, מתה במהלך כהונתה מסרטן בגיל ארבעים ואחת, כשבעלה ניסה להתמודד לנשיאות. היא הוחלפה בידי סגנה. השפעתו של וולאס בממשל נפסקה עד שנבחר שנית ב-1970. הוא היה ה"ג'נטלמן הראשון" במשך פחות משנה וחצי.
ריצתו לנשיאות ב-1968.
וולאס רץ לנשיאות ב-1968 כמועמדה של המפלגה העצמאית האמריקאית.
המפלגה הדמוקרטית דחתה את תמיכתו של וולאס בהפרדה גזעית. במהלך מסע הבחירות משך כמה מצביעים במדינות הדרום. הוא לא ציפה לנצח במערכת הבחירות, אבל ניסה למנוע משני המועמדים המובילים להשיג רוב בחבר האלקטורים וכך להעביר את הבחירות אל בית הנבחרים של ארצות הברית, שם יוכל להשפיע על בחירת המנצח.
התפתחות מסע הבחירות.
וולאס לא רץ לנשיאות ב-1968 כדמוקרט - כפי שעשה ב-1964 ויעשה שוב ב-1972 -אלא כמועמדה של המפלגה העצמאית האמריקאית. המפלגה הוקמה על ידו, לצורך תמיכה במדיניות של הפרדה גזעית. ב-1968 טען שאין כל הבדל בין שתי המפלגות הגדולות. הוא השתמש באסטרטגיה של מועמד הדמוקרטים הדרומיים, סטרום ת'ורמונד, שהתמודד ב-1948, ולא רצה לנצח בבחירות אלא קיווה להשיג מספיק אלקטורים כדי לאלץ את בית הנבחרים להכריע בבחירות, דבר שנחשב לאפשרות ריאלית. מצב זה היה נותן לו עמדת כוח: וולאס קיווה שמדינות הדרום ישתמשו בהשפעתן כדי לסתום את הגולל על ניסיון הממשלה לבטל את ההפרדה הגזעית.
במסע הבחירות הדגיש וולאס את הצורך בהחזרת החוק והסדר למדינה, ואת זכויות המדינות בנושאי ההפרדה הגזעית, מה שמשך את הדרומיים הלבנים והכפריים, ואת הפועלים המאוגדים בצפון. וולאס הוביל בבטחה במדינות הדרום עם 45% מהקולות באמצע ספטמבר. העובדה שמשך פועלים מאוגדים (שהיו תומכים מסורתיים של הדמוקרטים) פגעה ביוברט האמפרי במדינות צפוניות כמו אוהיו, אילינוי, ניו ג'רזי, ויסקונסין ומישיגן. סקר מאמצע ספטמבר חשף שזכה לתמיכה משליש מחברי האיגודים, ושבשיקגו השיג 44% מקולותיהם של פועלי תעשיית הפלדה, יותר מכל מועמד אחר. האמפרי וריצ'רד ניקסון הצליחו להקטין את התמיכה בוולאס עד לנובמבר. האיגודים הדגישו את זרימת העבודות מהצפון אל אלבמה של וולאס, שלא חייבה את העובדים להתאגד (אם כי וולאס תמך באיגודים), וניקסון, שחשש מפילוג של הקול השמרני, שכנע מספיק דרומיים שעליהם לתמוך בו כדי לעצור את האמפרי. מה-13 ל-20 באוקטובר, ירד וולאס מ-20% תמיכה ל-15%. בצפון, התחלקו קולותיו בצורה שווה בין האמפרי וניקסון. בדרום, בחרו שלושה רבעים מבוחריו בניקסון.
במצעו הציע וולאס תוספות תקציב גדולות לביטוח הלאומי ולמדיקר. מדיניות החוץ של וולאס הייתה שונה משני המועמדים האחרים. הוא טען שאם לא ישיג התקדמות במלחמת וייטנאם בתוך תשעים יום מכניסתו לתפקיד, הוא יצווה על נסיגה מידית. בנוסף הוא דרש שבעלות הברית האירופאיות והאסייתיות של ארצות הברית ישלמו יותר על ביטחונן. לצערו, עמדת סגנו המיועד, גנרל חיל האוויר בדימוס קרטיס לה מיי, פגעה בו לאחר שזה הציע להשתמש בנשק גרעיני בווייטנאם.