ב-1829 נבחר קריטנדן לבית הנבחרים של קנטקי לאחר שניצח בבחירות ביניים. הוא שימש כיושב ראש הבית במשך כל תקופת כהונה זו. ב-1830 הוא היה מועמד המפלגה הוויגית כמחליפו של ג'ן רואן בסנאט. שאיפתה החשאית של המפלגה הייתה לבחור בקליי, וכך להעניק לו קרש קפיצה למסע בחירות נוסף לנשיאות, אך לא היה ידוע אם הוא יהיה מסוגל להבטיח מספיק קולות לבחירתו. הוחלט שקריטנדן יהיה המועמד, ואם יסתמן לוויגים רוב בהצבעה בהפרש מספיק גדול, קריטנדן יפרוש ויאפשר להם לבחור בקליי תחתיו. מולו הציבו הדמוקרטים את ריצ'רד ג'ונסון, ג'ון רואן, צ'ארלס ויקליף וג'ון בריטהיט. אף אחד מהם לא הצליח להשיג יותר מ-64 הקולות מתוך 69 הקולות שהיו דרושים כדי לאשר את המועמדות. קריטנדן זכה ב-68 קולות ב-14 סבבי הצבעה שונים, אך סירב להצביע בעצמו, שכן הוא רצה שקליי יהיה המועמד. בכל אופן, כמה מאלו שהצביעו לקריטנדן, סירבו להצביע עבור קליי והמושב בסנאט נותר פנוי.
בשנה שלאחר מכן, רוב ברור של חברי בית הנבחרים של קנטקי נותר מחויב לקריטנדן לבחירתו לסנאט. עם זאת, בעלי בריתו של קליי לחצו על קריטנדן לפרוש מהמרוץ ולאפשר לקליי להיות מועמד הוויגים. קריטנדן נעתר וקליי נבחר ברוב של תשעה קולות מול ריצ'רד ג'ונסון. קריטנדן ניהל שני מסעות בחירות בלתי מוצלחים, האחד של ריצ'רד בנקר לתפקיד המושל והשני של קליי בקנטקי כמועמד בבחירות לנשיאות של 1832. לאחר תבוסתו של קליי ב-1832, הוא הציע שהוא יתפטר מהסנאט ויאפשר לקריטנדן להיבחר במקומו, אך קריטנדן דחה את ההצעה. מאוחר יותר באותה שנה התפטר קריטנדן מחברותו בבית הנבחרים של קנטקי.
פעילותו במפלגה הוויגית.
קריטנדן היה פעיל בארגון המפלגה הוויגית שהוקמה ב-1834 משרידיה של המפלגה הרפובליקנית הלאומית שחדלה לתפקד. ב-4 ביולי אותה שנה הוא זימן את הפגישה הארגונית הראשונה של המפלגה בקנטקי בקוב ספרינג, פרבר של פרנקפורט. הוא נבחר כיושב ראש הוועדה המקומית ובנאום שנשא למחרת היום הוא גינה במרירות את הנשיא ג'קסון. בהמשך אותה שנה מינה המושל ג'יימס מורהד את קריטנדן כמזכיר המדינה של קנטקי. בבחירות שנערכו באוגוסט זכו הוויגים ברוב בשני בתי המחוקקים של קנטקי. כאשר התכנסה האספה המדינתית, בחרו חבריה בקריטנדן כסנאטור מטעם המדינה על פניו של ג'יימס גתרי ברוב של 94 מול 40.
מיד לאחר שתפס את מושבו בסנאט, נבחר קריטנדן כחבר בוועדת האדמות הציבוריות וועדת המשפט של הסנאט, זאת בזכות ההשפעה של קליי. בראשית תקופת כהונתו זו הוא התנגד באופן נחרץ להצעתו של הסנאטור תומאס ה. בנטור להקצות תקציבים פדרליים לשדרוג קרקעות והקמת ביצורים צבאיים לאורך החוף המזרחי. הוא גם תקף את ממשל ג'קסון על הצו הנשיאותי שעל פיו נדרש תשלום בזהב או בכסף על קרקעות הממשלה. הוא ציין שהעקרונות של הצו הוצגו בהצעת החלטה שהוגשה לסנאט, אך נדחתה ברוב גדול. קריטנדן טען שדחיית ההצעה הייתה למעשה גינוי שלה על ידי הסנאט, ועדיין הממשל פעל בניגוד לכך חודשים ספורים לאחר מכן, וחרג, כפי שקריטנדן הגדיר זאת, ממגבלות הסמכות של הרשות המבצעת. הוא התעמת על הנושא באריכות עם בנטון והקונגרס העביר בסופו של דבר חוק שדרש מהממשלה לקבל את השטרות של הבנקים שהונפקו על פי הצו הנשיאותי לרכישת הקרקעות הממשלתיות, אך הנשיא ג'קסון לא חתם עליו עד להתפזרות הקונגרס, צעד שקרוי "וטו כיס" שנובע מאי נקיטת פעולה כלשהי על ידי הנשיא כדי שהחוק לא ייכנס לתוקף.
במהלך תקופת כהונתו זו בסנאט, נותר קריטנדן מבקר בוטה של ג'קסון ושל יורשו מרטין ואן ביורן. הוא תמך בתוכניתו של קליי לחלוקת ההכנסות ממכירת הקרקעות בין המדינות, ואף הצטרף לקליי בהתנגדותו ל שהממשל תמך בקיומה. אחת מההצעות היחידות של הממשל שבהן הוא תמך היה ההכרה ברפובליקת טקסס החדשה. במהלך תקופת כהונתו זו בסנאט בלטה במיוחד סוגיית העבדות. קריטנדן נחשב כבעל דעות מתונות בנושא, ששאף להותירו מחוץ לשיח הפוליטי. ב-1836 הוא התנגד לעצומות שהוגשו על ידי הקווייקרים לביטול העבדות בוושינגטון די. סי., אך הוא גם התנגד לצעדים הרדיקליים של תומכי העבדות כמו הצעתו של ג'ון קלהון לאסור את הפצתם של חומרים כתובים נגד העבדות באמצעות הדואר במדינות הדרום.
בניגוד לטבעו הפייסני, נקלע קריטנדן לעימות בין חברי הקונגרס ג'ונתן סילי ויליאם גרייבס, עימות שהסתיים בדו-קרב. באולם בית הנבחרים תקף סילי את יושרתו של עורך העיתון הוויגי, ג'יימס ווטסון ווב. ווב העביר דרישה באמצעות ידידו, ויליאם גרייבס, שסילי יחזור בו מדבריו. כאשר סירב סילי לקבל את המסר מגרייבס, האשים אותו גרייבס שהוא פגע בכבודו של ווב וקרא לו להתייצב מולו לדו-קרב. גרייבס, שאליו התלוו חברי הקונגרס ריצ'רד מנפי מקנטקי וריצ'רד וייז מווירג'יניה, ביקש מקריטנדן לשמש כ"משנה" שלו בדו-קרב. בתחילה מחה קריטנדן על כך, אך בסופו של דבר נעתר. לאחר שתי החטאות של שניהם, נהרג סילי בסבב הירי השלישי. לבית הנבחרים הוגשה הצעה להדיח את גרייבס ולגנות את שאר המשתתפים בדו-קרב, להוציא את קריטנדן שהיה סנאטור ולפיכך לא כפוף לבית הנבחרים. ההחלטות על ההדחה והגינוי הורדו בסופו של דבר מעל סדר היום, אך קריטנדן חש באופן אישי ייסורים על מה שקרה והתחרט על מעשיו.
ממשלי הריסון וטיילר.
בבחירות לנשיאות של 1840 עודד קריטנדן שוב את הוויגים בקנטקי לתמוך במועמדותו של הנרי קליי. במהלך ההצבעה בוועידה הארצית של המפלגה ב-1839, קיימו המועמדים קליי והגנרל וינפילד סקוט עם קריטנדן ועם איש המפלגה ג'ורג' אוונס משחק קלפים בבית אסטור בניו יורק. כאשר הם קיבלו את ההודעה על ניצחונו של ויליאם הנרי הריסון, האשים קליי בהפסדו את סקוט והכה אותו בכתף שבה הוא נפצע במהלך השתתפותו בקרב לנדיס ליין במלחמת 1812. לאחר מכן היה צורך להוציא את קליי בכוח מהמלון. סקוט שלח אז את קריטנדן לקליי עם קריאה לדו-קרב, אך קריטנדן גרם לפיוס בין השניים ושיכנע את קליי להתנצל.
לאחר שקליי הפסיד את המועמדות, תמך קריטנדן בהריסון. באותה מערכת בחירות הוא נבחר מחדש לסנאט, אף על פי שהוא ציפה לקבל משרה בקבינט של הריסון. בסופו של דבר הוא מונה כתובע הכללי של ארצות הברית. לצורך כך הוא התפטר מהסנאט.
כתובע הכללי, הוציא קריטנדן רק חוות דעת משמעותית אחת. העותר בתיק זה היה אדם שרכושו ניזוק במהלך פלישתו של אנדרו ג'קסון לשטח שהפך ב-1818 לטריטוריית פלורידה. ב-1841 התיק היה עדיין בדיונים. בית משפט בפלורידה פסק לטובת התובע והורה לממשלה הפדרלית לפצותו על הנזקים ולשלם ריבית על סכום התביעה בחישוב החל מהמועד בו נגרם הנזק. מזכיר האוצר תומאס יואינג שאל את קריטנדן אם לבית המשפט הייתה הסמכות להורות על תשלום ריבית. קריטנדן סבר שלבית המשפט לא הייתה הסמכות לכך, ויואינג לא שילם את הריבית. חוות דעתו של קריטנדן שמשה תקדים במקרים דומים בהמשך על ידי התובעים הכלליים שכיהנו אחריו.
שבוע בלבד לאחר שמונה כתובע הכללי, נשלח קריטנדן לניו יורק כדי לגשר במתיחות עם בריטניה על הטבעת הספינה קרוליין על ידי כוח מיליציה קנדי, שניסה לדכא מרד בקנדה. במשימה דיפלומטית זו פעל קריטנדן בנפרד ממשימותיו כתובע הכללי. הוא דיבר עם מושל ניו יורק ויליאם סיוארד, וקיבל ממנו הבטחה שהוא יעניק חנינה לאלכסנדר מקלאוד שלכד את הקרוליין והעלה אותה באש, אם הוא יורשע במשפט בניו יורק. בסופו של דבר זוכה מקלאוד.
זמן קצר לאחר פרשת הקרוליין, נפטר הנשיא הריסון, וסגן הנשיא ג'ון טיילר הושבע במקומו. טיילר התנגד לניסיונו של קליי לקבוע את סדר היום של המפלגה הוויגית, והטיל וטו על שתי הצעות חוק בתחום הבנקאות בניגוד לעצתו של קריטנדן. קריטנדן ושאר הוויגים בקבינט, למעט דניאל ובסטר, התפטרו במחאה על חריגתו של טיילר מהקו המפלגתי. התפטרותו של קריטנדן נכנסה לתוקף ב-11 בספטמבר 1841. הוא שב לקנטקי ללא משרה פוליטית ועם מעט כסף ברשותו. קבוצה של ידידים שלו במחוז וודפורד רכשה את הבית בו הוא גדל כילד והגישה לו אותו כמתנה בשובו לקנטקי.
ב-1842 מונה קריטנדן שוב כסנאטור כדי לאייש את המושב שהתפנה עם התפטרותו של הנרי קליי. בינואר 1843 הוא נבחר מחדש לתקופת כהונה מלאה לאחר שהתמודד מול ריצ'רד ג'ונסון. הסכסוך של הוויגים עם הנשיא טיילר המשיך ללא הפוגה, וכמה מהם דיברו בפתיחת הליך הדחה נגדו, אך קריטנדן התנגד לצעד זה. בשנים 1841–1845 הוא היה יושב ראש הוועדה לענייני הצבא של הסנאט. הוא תמך בהטלת מכסי מגן באופן מתון ובביצוע עבודות ציבוריות על ידי הממשלה הפדרלית. הוא התנגד למתן זכות למדינות לקבוע את חלוקתן למחוזות בחירה, כך שיתאפשר להן לבחור את נציגיהם לקונגרס בבחירות בהן השטח של כל אחת מהמדינות היווה מחוז בחירה אחד.
ממשל פולק.
גם בבחירות של 1844 תמך קריטנדן במועמדותו לנשיאות של קליי. קליי נחשב בעיני רבים לא רק כמועמד המועדף מטעם הוויגים, אלא גם כבעל סיכויים גבוהים לזכייה בבחירות הכלליות. אף אחת מהסוגיות המסורתיות של מסע הבחירות - "תפישת השלטון בכוח" של טיילר, "העסקה המושחתת" של קליי עם ג'ון קווינסי אדמס, או מכסי המגן - לא נראו ככאלו שמשכו את תשומת ליבם של ציבור הבוחרים. בכל אופן, סוגיית סיפוחה של טקסס שינתה כליל את פני מערכת הבחירות. קליי ערך סיור בדרום זמן קצר לפני שוועידת המפלגה הוויגית הגיעה למסקנה שהדעות בעד הסיפוח בחלק זה של ארצות הברית לא היו נחרצות כפי שסברו בוושינגטון. בניגוד לדעה זו ובניגוד לעצתו של קריטנדן, שלח קליי מכתב בו הוא הביע את התנגדותו לסיפוח וביקש שיפורסם בעיתון National Intelligencer.