In 1998, he became an assistant coach for the Sonics and in 2000, was named interim head coach. He remained the Sonics' floor general until July 2005, when he left the Emerald City for Portland.
Even though McMillan spent only two seasons with the Wolfpack, just suiting up for them was a dream come true for the North Carolina native.
"It was a great two years," he said. "I came in after the national championship (in 1983). I was always a Wolfpack fan after growing up in Raleigh. I never dreamed that I would one day play in that Red and White. To have the opportunity to play ACC basketball at the college that I love the most was just a fantasy for me.
"To come there after the national title team and when everybody was talking about NC State basketball and Jimmy V(alvano), it was just a really special time. To play my two years there and get to the (NCAA) Final Eight both times, it was a great two years of my life."
Playing for Valvano didn't just impact him as a player, it also continues to influence how he coaches.
"A lot of people didn't give him the credit I thought he deserved as a coach," McMillan said. "He was a good x-and-o coach. He knew how to communicate with his players and motivate his teams. That is the one thing I try to take from him, is how he motivated his team. You would be in the locker room listening to him give his pregame speech and would be on the edge of your seat. You would do anything you could for him and for NC State basketball."
In 1986, Nate was a second-round pick of Seattle in the NBA Draft and played 12 seasons for the Sonics before retiring in 1998. That was when he made the quick transition from NBA player to coach.
"When I was about to retire from playing, (Seattle head coach) George Karl wanted me to come along and be an assistant," he said. "Seattle's organization wanted me to continue being part of their organization. I didn't know exactly where I would go at the time, but I knew I would be working for the Sonics. It just so happened that George left the following year and the organization wanted to keep me involved with the team, so I became an assistant coach."
"Just two years later, I became the head coach," McMillan recalled. "The transition (to coaching) wasn't as difficult as I thought it would be. I always have tried to lead by example. By doing that as a player and assistant (coach), they felt that I could lead an NBA team and become a head coach. They made that decision to give me the head coaching job, extended my contract and spent a number of years there."
After becoming the Sonics' head coach in 2000, Nate had a successful run in Seattle, including leading them to the 2004-05 Northwest Division title, he left to become Portland's new head coach in July 2005. Leaving a city where he had spent so many years was tough for McMillan, but he admits it was time for a change of venue.
"It was just time for change," McMillan stated. "In everyone's life, that will happen. For me, a guy who had spent 20 years there as a player and coach, it was time for me to leave and there was an opportunity for me to move on. I wanted to challenge myself with another coaching opportunity. I had given all that I felt I could to Seattle and didn't feel like I could give any more to them than I already had and I wanted to leave there on good terms. I felt like I had gotten everything from my players there and you really can't do much more than that.
"Portland gave me that opportunity. It wasn't difficult because it felt right at the time. It was time to do something different."
Many Sonics fans scratched their heads as to why McMillan would bolt for the Trail Blazers, especially considering the less-than-stellar reputation that the "Jail Blazers," as they were referred to at the time because of their numerous appearances on the police blotter. For Nate, it all boiled down to one thing... a new challenge.
"I know what I believe in and what I represent," he said. "I know that it was a black mark on the team and knew that I wanted to be a part of changing it. I knew it was a great opportunity. The organization wanted to change and that started with getting the right kind of coach in here. Being a young coach and not a guy with a lot of success but who had a vision. They felt like my vision and theirs were pretty much the same. They wanted to see if we could change the perception of this organization. For me, I felt like I could take a job like this. I wasn't one of those guys who had been around so long that he couldn't take a job like this. It will help me grow as a coach. I hope that I can help the organization and make this a long-lasting relationship."
Since arriving in Portland, McMillan has assembled a solid roster with some of the best young talent in the NBA. Brandon Roy could be the league's rookie of the year this season and fellow rookie LaMarcus Aldridge was also a lottery pick who has performed well in his first year in the Association.
"We are continuing to put it together and are trying to transform this team," he said. "Last year was my first year and that was the start of changing the direction and perception of this team. We made a number of trades during the draft this year and got some very young talent that we feel in the future, not only will they represent us on the floor well, but off the floor well.
"Character and individual talent were important (in those players) and we got those things. We're not winning a lot of games right now but we do like the direction that we're going. We felt like we had to start over with this organization and really build it from the ground up. Now, we've started and it's just a matter of getting guys developed and adding some guys to our roster. In the next few years, we feel like we will be back to where this team was in 1990s, one of the top teams in the league."
After a successful run both as an NBA player and head coach in Seattle, former NC State men's basketball player Nate McMillan is seeking the same success in Portland. In 2005, he took on the sizeable task of helping to elevate the Trail Blazers from NBA also-ran to league powerhouse, a position they held in the 1990s. Now in his second season on the job, Nate has made great strides in building a roster stocked with the right mix of solid young talent and seasoned veterans to help speed the process along as quickly as possible. In the coming years, Portland could indeed become a force in the Western Conference and if they do, a great deal of the credit will go to McMillan.