Utah Jazz (2006–2013)

Dort wurde er erst in der zweiten Runde an 47. Stelle von den Utah Jazz ausgewählt, bei denen er bis zum Sommer 2013 spielte. In seinen ersten beiden Spielzeiten brachte es Paul Millsap auf 7,5 Punkte und 5,4 Rebounds im Schnitt. Der Durchbruch gelang ihm in der Spielzeit 2008/2009, in der er dank eines Durchschnitts von 13,9 Punkten und 8,9 Rebounds eine Verletzung des nominellen Power Forwards Carlos Boozer vergessen machte.

In 19 Spielen vom 24. November 2008 bis zum 7. Januar 2009 erzielte er jeweils zweistellige Werte in den Kategorien Punkte und Rebounds. So viele aufeinanderfolgende Double-doubles hatte bei den Jazz zuletzt John Stockton erreicht, der es in der Saison 1990/91 auf 25 Double-doubles in Serie brachte.

Im Sommer 2009 nahm Millsap als Restricted Free Agent ein Angebot der Portland Trail Blazers an. Die Jazz hatten sieben Tage Zeit, um mit dem Angebot der Blazers gleichzuziehen und Millsap zu halten, was sie schlussendlich taten. Da Boozer wieder in guter körperlicher Verfassung war, erhielt Millsap etwas weniger Spielzeit als im Vorjahr und kam für die Jazz als bester Bankspieler auf 11,6 Punkte und 6,8 Rebounds im Schnitt.

Nachdem Boozer im Sommer 2010 die Jazz verlassen hatte, übernahm Millsap seine Rolle als Stammspieler auf der Power-Forward-Position. Am 9. November 2010 erzielte Millsap während einer Partie gegen die Miami Heat in den letzten 28 Sekunden des vierten Viertels elf Punkte. Er verwandelte dabei drei Würfe von jenseits der Dreipunktelinie, mehr als in allen Spielen seiner vorherigen NBA-Karriere zusammen. Insgesamt erzielte er in diesem Spiel eine neue persönliche NBA-Bestmarke von 46 Punkten. In der Saison 2010/11 stand Millsap in allen 76 Spielen in der Anfangsaufstellung und erzielte bisherige persönliche NBA-Höchstwerte in Punkten (17,3 pro Spiel) und Assists (2,5 pro Spiel). Auch in den beiden darauffolgenden Spielzeiten war Millsap in Utah als Power Forward gesetzt. Zwischen 2007 und 2010 sowie 2012 erreichte er mit Utah die Playoffs.

Atlanta Hawks (2013–2017)

Nach Ablauf seines Vertrages bei den Jazz im Sommer 2013 verließ Millsap die Mannschaft und unterzeichnete einen Vertrag bis 2015 bei den Atlanta Hawks. Im Jahre 2014 wurde Millsap erstmals in das NBA All-Star Game berufen. Am 18. März 2014 gelang Millsap beim 118:113-Sieg über die Toronto Raptors mit 19 Punkten, 13 Rebounds und 10 Assists sein erstes Triple-Double. Millsap erzielte in diesem Jahr mit 17,9 Punkten und 3,1 Assists pro Spiel wieder neue Karrierebestwerte. Mit den Hawks erreichte er die Playoffs, wo man sich in der ersten Playoffrunde nach sieben Spielen den Indiana Pacers geschlagen geben musste. Im Jahr 2015 erhielt Millsap seine zweite All-Star-Nominierung. Mit den Hawks erreichte Millsap den ersten Platz in der Eastern Conference, welche sich somit den Heimvorteil in den Playoffs sicherten. Dort stieß er mit der Mannschaft bis in die Finalspieler der Eastern Conference vor, in denen man den Cleveland Cavaliers unterlag. Am 9. Juli 2015 unterschrieb Millsap als Free Agent einen Dreijahresvertrag bei den Hawks, der ihm ein Gehalt von 59 Millionen US-Dollar zusicherte. Millsap wurde 2016 zum dritten Mal zum All-Star-Game eingeladen. Mit Atlanta erreichte er auch 2016 die Playoffs. Im vierten Spiel der ersten Runde gegen die Boston Celtics erzielte Millsap mit 45 Punkten einen persönlichen Playoffrekord. Das Spiel wurde jedoch verloren. 2017 erhielt er seine bisher letzte All-Star-Nominierung und spielte eine starke Saison für die Hawks, die er mit 18,1 Punkten pro Spiel beendete.

Denver Nuggets (2017–2021)

Millsaps Vertrag bei den Hawks lief im Sommer 2017 aus. Seiner Aussage zufolge bot Atlanta ihm keine Verlängerung an. So unterschrieb Millsap einen Dreijahresvertrag bei den Denver Nuggets, in dem ein Gesamtgehalt von 90 Millionen US-Dollar festgeschrieben war. Millsap verletzte sich im November 2017 am linken Handgelenk und fiel mehrere Wochen aus. Er kehrte im Februar 2018 zurück und kämpfte mit den Nuggets um den letzten Playoffplatz, den man am letzten Spiel im direkten Duell mit den Minnesota Timberwolves verlor. Millsap absolvierte nur 38 Saisonspiele und erzielte dabei 14,6 Punkte und 6,4 Rebounds im Schnitt.

Nachdem Millsap 2020 vertragslos geworden war, unterschrieb er eine 10 Millionen US-Dollar dotierten Einjahresvertrag-Verlängerung bei den Nuggets.

Brooklyn Nets (2021–2022)

Im Sommer 2021 wechselte Millsap zu den Brooklyn Nets. In der Saison 2021/22 bestritt er 24 Spiele für Brooklyn, seine mittlere Einsatzzeit lag bei rund elf Minuten und war damit deutlich geringer als im vorherigen Verlauf seiner NBA-Laufbahn. Er kam auf 3,4 Punkte je Begegnung.

Philadelphia 76ers (Seit 2022)

Im Februar 2022 wurde Millsap zusammen mit James Harden an die Philadelphia 76ers abgegeben.

Reguläre Saison

Play-offs