Στις [[7 Μαρτίου]] [[2004]], ως αρχηγός της [[Νέα Δημοκρατία|Νέας Δημοκρατίας]], ανεδείχθη νικητής στις [[Ελληνικές βουλευτικές εκλογές 2004|βουλευτικές εκλογές]] με ποσοστό 45,36% εξασφαλίζοντας κοινοβουλευτική πλειοψηφία 164165 εδρών επί συνόλου 300. Έλαβε εντολή σχηματισμού κυβέρνησης από τον [[Πρόεδρος της Ελληνικής Δημοκρατίας|Πρόεδρο της Δημοκρατίας]] και στις 10 Μαρτίου ορκίστηκε Πρωθυπουργός και [[Υπουργείο Πολιτισμού|υπουργός Πολιτισμού]]. Στον ανασχηματισμό της 14ης Φεβρουαρίου [[2006]] παραιτήθηκε από το χαρτοφυλάκιο του [[Υπουργείο Πολιτισμού|Υπουργείου Πολιτισμού]].
Το 2007 προκήρυξε πρόωρες [[Ελληνικές βουλευτικές εκλογές 2007|εκλογές]], τις οποίες κέρδισε η [[Νέα Δημοκρατία]] στις 16 Σεπτεμβρίου, εξασφαλίζοντας ποσοστό 41,8% και 152 έδρες στη Βουλή, έναντι 38,1% για το [[Πανελλήνιο Σοσιαλιστικό Κίνημα|ΠΑΣΟΚ]] και 102 έδρες. Την επόμενη ημέρα των εκλογών ο Καραμανλής έλαβε εντολή για σχηματισμό νέας κυβέρνησης από τον [[Πρόεδρος της Δημοκρατίας|Πρόεδρο της Δημοκρατίας]], [[Κάρολος Παπούλιας|Κάρολο Παπούλια]]. Η κυβέρνηση αυτή ορκίστηκε και ανέλαβε καθήκοντα στις 19 Σεπτεμβρίου 2007.
[[File:Fontana Aleksandar $ (3).JPG|thumb|Το ''Αγαλμα του έφιππου πολεμιστή'' στην [[πλατεία Μακεδονίας]] των [[Σκόπια|Σκοπίων]].]]
Το 2007, όταν ΥπΕξ ήταν πλέον η [[Ντόρα Μπακογιάννη]], η ελληνική κυβέρνηση είχε την πρόθεση διεξαγωγής συνομιλιών για την επίλυση του ζητήματος στο τέλος του έτους μετά τις σχεδιαζόμενες εκλογές, αλλά η [[εθνικισμός|εθνικιστική]] προπαγάνδα της κυβέρνησης [[Νίκολα Γκρούεφσκι|Γκρούεφσκι]], με τη μετονομασία του [[Διεθνής Αερολιμένας Σκοπίων|αεροδρομίου]] και την [[Σκόπια 2014|ανέγερση αγαλμάτων]], που προκάλεσε την αντίδραση κυρίως ψηφοφόρων στη βόρεια Ελλάδα, ανέστειλε την έναρξή τους. Η Μπακογιάννη δήλωσε τη θέση της υπέρ της αναβολής ένταξης της πρώην Γιουγκοσλαβικής Δημοκρατίας της Μακεδονίας στο ΝΑΤΟ για το 2009 στον αμερικανό πρεσβευτή, ο οποίος διαφώνησε.<ref name=Wikileaks-EfSyn20180128/> Μία εβδομάδα πριν τις [[Ελληνικές βουλευτικές εκλογές του 2007|βουλευτικές εκλογές του 2007]] ο Καραμανλής εξήγγειλε ότι θα έθετε βέτο στην ένταξη της γειτονικής χώρας στο ΝΑΤΟ αν δεν είχε επιλυθεί προηγουμένως το ζήτημα της ονομασίας της.<ref name=Wikileaks-EfSyn20171227>{{cite news|url=http://www.efsyn.gr/arthro/kyriakos-me-syntagi-samara|title=Κυριάκος με... συνταγή Σαμαρά|author=Δημήτρης Ψαρράς|newspaper=[[Η Εφημερίδα των Συντακτών]]|date=27-12-2017|accessdate=01-02-2018}}</ref> Στις προγραμματικές δηλώσεις της [[κυβέρνηση Κώστα Καραμανλή 2007|νέας κυβέρνησης]] μετά τις εκλογές η Μπακογιάννη εξήγγειλε τη θέση της κυβέρνησης υπέρ μιας σύνθετης ονομασίας. Σε συνάντηση με τον Αμερικανό πρεσβευτή τον Ιανουάριο του [[2008]] ο Καραμανλής δήλωσε ότι θα αποδεχόταν οποιαδήποτε σύνθετη ονομασία με δεύτερο συνθετικό τη λέξη «Μακεδονία» ή την υιοθέτηση μιας διπλής ονομασίας, αν η σύνθετη ονομασία χρησιμοποιούνταν από τις [[ΗΠΑ]] και σε όλους τους διεθνείς οργανισμούς.<ref name=Wikileaks-EfSyn20180122>{{cite news|url=https://www.efsyn.gr/arthro/k-karamanlis-nea-voreia-opoiadipote-makedonia|title=Κ. Καραμανλής: «Νέα, Βόρεια, οποιαδήποτε Μακεδονία»|author=Δημήτρης Ψαρράς|newspaper=[[Η Εφημερίδα των Συντακτών]]|date=22-01-2018|accessdate=01-02-2018}}</ref> Το Μάρτιο η Μπακογιάννη διαμήνυσε στον αμερικανό πρεσβευτή την ανάγκη εύρεσης μιας οριστικής σύνθετης ονομασίας με πρώτο συνθετικό το "Άνω" ή το "Νέα" που θα ίσχυε έναντι όλων (erga omnes).<ref name=Wikileaks-EfSyn20180128/> Σε συζήτηση στη [[Βουλή των Ελλήνων]] τον Απρίλιο του 2008 με τη θέση της κυβέρνησης Καραμανλή υπέρ μιας σύνθετης ονομασίας συντάχθηκαν όλα τα κοινοβουλευτικά κόμματα εκτός από το [[ΛαΟΣ]].<ref name=Wikileaks-EfSyn20180122/>
[[File:North Atlantic Council Summit Meeting (2008).jpg|thumb|H [[Σύνοδος κορυφής του ΝΑΤΟ 2008 (Βουκουρέστι)|Σύνοδος Κορυφής του ΝΑΤΟ]] στο [[Βουκουρέστι]] το 2008.]]
