אחרי שנכנס לתפקיד, ארגן קרמנליס מחדש את "ההתלכדות היוונית" במפלגה חדשה שנשאה את השם "האיחוד הלאומי הרדיקלי". אחד החוקים הראשונים שקידם היה החוק האלקטורלי שהעניק זכויות הצבעה מלאה לנשים, שלא יושם עדיין אף על פי שאושר עוד בשנת 1952. קרמנליס זכה להמשיך לנהל את הממשלה בעקבות ניצחון בשלוש מערכות בחירות רצופות בפברואר 1956, במאי 1958 ובאוקרטובר 1961.
במדיניות הפנים.
בשנת 1959 הודיע על תוכנית חומש (1964-1960) שנועדה לקדם את כלכלת יוון, על ידי שיפור התפוקה בחקלאות ובתעשייה, השקעות גדולות בתשתיות ועידוד התיירות.
ממשלתו השיגה הכפלת התוצר הלאומי הגולמי, צמיחה כלכלתי שנתית של 6.25 % בממוצע, עלייה בהכנסה מ-305$ ל 565 $ לתושב, והורדת שיעור האינפלציה ל-2 %. קודם הייצור, חוזקה התוצרת המקומית, התפתחו הספנות, גברו ההשקעות של הון זר.
עם עבודות התשתית החשובות שנערכו באותן השנים נמנתה הכביש פטרס-אתונה-סלוניקי-אבזוני. בתחם הרווחה הוקם ארגון הקצבאות בחלקאות.
ב-1959 הודיע קרמנליס על השקת תוכנית חומש (1964-1959) לכלכלת יוון, עם דגש על שיפור התוצרת החקלאית והתעשייתית, השקעות כבדות בתשתיות, קידום תיירות, שהיוו בסיס ל"נס הכלכלי היווני אחרי המלחמה".
במדיניות החוץ.
בזירה הבינלאומית קרמנליס שיפר את היחסים עם יוגוסלביה.
היחסים עם טורקיה ועם הממלכה המאוחדת נותרו מתוחים על רקע המתח הבינאתני בקפריסין.
מתוך רצון לשים קץ לסכסוך ולשפר את הקשר בין יוון לשאר חברות נאט"ו נטש קרמנליס את היעד האסטרטגי הקודם של הממשלה - האיחוד ("אנוסיס") עם קפריסין והתחיל לתמוך בעצמאותה של קפריסין.
בשנת 1958 התחיל במשא ומתן עם בריטניה וטורקיה שהניב בשנת 1959 את הסכם ציריך לפיו גובשה תוכנית לקידום עצמאותה של קפריסין. התוכנית נכפתה כ"עובדה מוגמרת" על המנהיגים של היוונים והטורקים באי. בסופו של דבר היא קיבלה באותה שנה בלונדון גם את אישורו של המנהיג הקפריסאי-יווני, הארכיבישוף מקאריוס.
קרמנליס הואשם על ידי האופוזיציה בבגידה בעניין הלאומי היווני ובכניעה לאינטרסים של ברית נאט"ו ושל ארצות הברית.
קרמנליס חיזק את יחסי ארצו עם הברית נאט"ו ועם העולם הערבי
פרשת מרטן.
באותה תקופה פרצה פרשה הידועה כפרשת מנטן. מקס מרטן היה בזמנו יועץ של המנהל הצבאי הגרמני תחת הכיבוש הנאצי בסלוניקי. הוא נשפט ביוון, הורשע ונידון בשנת 1959 ל-25 שנות מאסר על פשעי מלחמה. אולם ב-3 בנובמבר 1959 קיבל מרטן חנינה, שוחרר לחופשי וגורש לגרמניה המערבית בעקבות לחצים פוליטיים וכלכליים גרמנים. באותה תקופה גרמניה המערבית אירחה כבר אלפי מהגרים כלכליים מיוון.
מעצרו של מרטן ומשפטו קומם במיוחד את מלכת יוון פרדריקה, שהייתה ממוצא גרמני ונכדתו של הקייזר וילהלם השני. היא תמהה "באיזה אופן הבין תובע מחוזי את התפתחות היחסים בין גרמניה ובין יוון".
בהגיעו לגרמניה המערבית, מרטן זוכה מכל ההאשמות מ"חוסר ראיות". ב-28 בספטמבר 1960 פרסמה התקשורת הגרמנית באמצעות "המבורגר אכו" והמגזין "דר שפיגל" קטעים מעדותו של מרטן בפני הרשויות הגרמניות, שבה טען כי קרמנליס, שר הפנים טקיס מקריס ואשתו דוקסולה (אותה תיאר כ"אחייניתו" של קרמנליס) וסגן שר הביטחון גיורגוס תמליס היו בזמנו מלשינים בשירות הכובשים הנאצים. לדברי מרטן, קרמנליס ומקריס אף תוגמלו על שירותיהם באמצעות קבלת עסק בסלוניקי שהשתייך קודם ליהודי יווני שנשלח לאושוויץ. הוא הוסיף שעל רקע זה הפעיל לחצים על קרמנליס ועל מקריס כדי לזכות בחנינה ובשחרור מן הכלא.
קרמנליס דחה את הטענות כחסרות בסיס ומופרכות והאשים את מרטן בניסיון לסחוט ממנו כסף לפני ששטח את האשמותיו. הממשלה המערב-גרמנית תיארה גם היא את ההאשמות כהשמצות והוצאת דיבה. קרמנליס האשים מפלגת אופוזיציה יריבה במסע הכפשות נגדו.
אף על פי שקרמנליס עצמו לא פתח בהליכים משפטיים נגד מרטן, טקוס ודוקסולה מקריס וגם תמליס תבעו את המגזין "דר שפיגל" על הוצאת דיבה. בשנת 1963 אכן מצא בית המשפט ביוון כי "דר שפיגל" חטא בלשון הרע. מרטן לא הופיע בדיוני בית המשפט היווני. פרשת מרטן נשארה באור הזרקורים עד תחילת שנת 1961.
האשמותיו של מרטן נגד קרמנליס לא נידונו כלל בפני בית משפט כלשהו. ההיסטוריון יאניס קטריס, מבקר חריף של קרמנליס, סבר שקרמנליס היה צריך להתפטר מראשות הממשלה ולתבוע את מרטן כאדם פרטי בבתי המשפט הגרמניים כדי לטהר לחלוטין את שמו. עם זאת גם קטריס דוחה את ההאשמות של מרטין כ"חסרות בסיס" ו"כוזבות ללא ספק".
החזון האירופי.
כבר ב-1958 הוביל קרמנליס בעקביות עיקשת את סוגיית הצטרפותה של יוון לשוק המשותף האירופי. הוא ראה בשאיפה זו חלום אישי, מה שהוא תיאר כהגשמת "הייעוד האירופי של יוון". הוא סבר כי התקבלות יוון כחלק ממשפחת הלאומים של מערב אירופה הדמוקרטי תעזור להבטיח למולדתו את היציבות הפוליטית הרצויה. קרמנליס הרבה לסנגר על השקפה זו באוזני המנהיגים האירופיים החל מהקנצלר קונראד אדנאואר ועד לשארל דה גול וניהל לאחר מכן בבריסל משא ומתן אינטנסיבי במשך שנתיים. הוא ראה באומה היוונית - יחידה אתנית מיוחדת החיה בגבול בין העולם הסלאבי לעולם הטורקי והשייכת למערב האירופי.
אכן הקמפיין שהוביל הניב פירות וב-9 ביולי 1961 חתמה ממשלת יוון עם השוק המשותף על פרוטוקולים לחוזה השותפות של יוון עם הקהילה הכלכלית האירופית. בטקס התחימה באתונה השתתפו משלחות רמות דרג מגרמניה (בראשות סגן הקנצלר לודוויג ארהרד), מצרפת, איטליה, בלגיה (בראשות שר החוץ פול-אנרי ספאק, אחד מאבות המיזם האירופי), לוקסמבורג והולנד. נכח גם שר הכלכלה של יוון, אריסטידיס פרוטופפדקיס, ושר החוץ שלה, אוונגלוס אוורוף.
ההסכם השפיע עמוקות על הוצאתה של יוון מהבידוד הכלכלי והפרה את תלותה הכלכלית והמדינית בסיוע הכלכלי והצבאי של ארצות הברית, בעיקר באמצעות נאט"ו. יוון הפכה למדינה האירופית הראשונה שזכתה במעמד של מדינה שותפה לשוק האירופי, מחוץ לשש המדינות המייסדות.
בנובמבר 1962 נכנס הסכם השותפות לתוקף והיווה בסיס לדרך לחברות מלאה בקהילה הכללית האירופית עד שנת 1984, אחרי סילוק כל המכסים היווניים על הייבוא מהשוק המשותף. פרטי-כל ההסכם כלל סעיף פיננסי שפתח את אפשרות להלוואות מסובסדות במשך 10 שנים (1972-1962) ליוון בשווי של 300,000,000 דולר, שהיו אמורות לשפר את התחרותיות של כלכלת יוון כהכנה לכניסה למעמד של חברות מלאה בקהילה.
חבילת הסיוע הפיננסי ופרטי כל ההצטרפות הושהו בשנים 1974-1967, שנות הדיקטטורה הצבאית במדינה. יוון הורחקה אז מהשוק האירופי ועזבה גם את מועצת אירופה, כדי להתחמק מהחקירות של פורום זה בנוגע להאשמות בשימוש בעינויים.
אחרי החזרה לדמוקרטיה, בשנת 1975 חידש קרמנליס את מאמציו לקבלת יוון כחברה מלאה באיחוד האירופי.
הוא היה משוכנע שהחברות בקהיליה האירופית תבטיח ליוון את היציבות הפוליטית הרצויה במעבר מדיקטטורה לדמוקרטיה.
במאי 1979 היה לו הסיפוק לחתום את הסכם ההצטרפות המלאה לקהיליה האירופית. בהתאם לחזונו יוון הפכה ב-1 בינואר 1981 לחברה העשירית של האיחוד האירופי, וזאת שלוש שנים לפני המועד שנקבע בפרטי כל.
המשבר הפוליטי הממושך ויציאתו לגלות מרצון.
בבחירות בשנת 1961 זכה האיחוד הלאומי הרדיקלי של קרמנליס ב-50.8% מהקולות ו-176 מושבים בפרלמנט. ב-31 באוקטובר הצהיר גאורגיוס פפנדראו, מנהיג "איחוד המרכז" שתוצאות ההצבעה הושפעו על ידי זיופים והטייה לא כשרה של הקולות. היו טענות על שימוש בקולות של נפטרים ובהפחדה. איחוד המרכז טען שתוצאות הבחירות בוימו לפי תוכנית מכונה בקוד "פריקלס" על ידי סוכני צללים "חוץ-ממלכתיים" (παρακράτος), לרבות מפקדי צבא, שירות המודיעין של יוון ו"גדודי ההגנה של הממשר הלאומי" הימני הקיצוני. המחנה השמאלי המיוצג על ידי EDA סירב להכיר בתוצאות הבחירות. אף על פי שאי סדירויות קרו באמת, קיומה של תוכנית "פריקלס" לא הוכחה לעולם. גם לא הוכח שההתערבויות השרירותיות בבחירות השפיעו באופן משמעותי את התוצאות. לדעת קרמנליס באי סדירויות בהצבעה היו מעורבים החוגים מסביב למלך. באווירה שנוצרה חלה הסלמה במתח הפוליטי, כשפפנדראו סירב להכיר בממשלת קרמנליס. ב-14 בנובמבר 1961 יצא פפנדראו למה שנקרא "המאבק הבלתי פוסק" ("ανένδοτος αγών") נגד קרמנליס.
המתח בין קרמנליס למשפחת המלוכה עלה כשהטיל קרמנליס וטו נגד מימונם של פרויקטים שיזמה המלכה פרדריקה. ב-17 ביוני 1963, אחרי חילוקי דעות עם המלך פבלוס, קרמנליס התפטר מראשות הממשלה ויצא לחו"ל בהתחלה למשך 4 חדשים. בינתיים הארץ סערה בעקבות רציחתו של ד"ר גרגוריס למבראקיס, חבר בפרלמנט מטעם השמאל, על ידי קיצונים ימניים, בזמן הפגנה למען השלום בסלוניקי.
האופוזיציה הוקיעה את קרמנליס כשותף מוסרי לרצח.
בבחירות בשנת 1963 הובס האיחוד הלאומי הרדיקלי בראשות קרמנליס על ידי איחוד המרכז שבראשות גאורגיוס פפנדראו. כשהוא מאוכזב עזב קרמנליס את יוון תחת הזיהוי המזויף "טריאנדפילידיס". הוא נשאר 11 שנה בגלות מרצון בפריז. במקומו התמנה בראשות הממשלה פנאיוטיס קנלופולוס, יורשו של קרמנליס בראשות המפלגה ERE (המפלגה הלאומית הרדיקלית)
בשנת 1966 שלח המלך קונסטנדינוס השני את שליחו דמטריוס ביציוס לפריז במשימה לשכנע את קרמנליס לשוב ליוון ולחזור לזירה הפוליטית. לפי עדות מאוחרת של המלך, בשנת 2006, אחרי ששני האישים לא היו כבר בחיים, נחשף שקרמנליס השיב לביציוס שיחזור ליוון רק בתנאי שהמלך יכריז על מצב חירום, בהתאם לסמכויות שעמדו לרשותו.
ממושבו בגלות הוקיע קרמנליס את משטר הקולונלים שהתשלט על יוון ב-21 באפריל 1967
רצח למברקיס.