Notebaert had been chief executive officer and president of network equipment maker Tellabs since 2000 and before that was chairman and chief executive officer of regional US phone company Ameritech.
Notebaert said he would work on "increasing Qwest's credibility with Wall Street" and plans to meet with customers to make relationships stronger.
Working with the US Federal Communications Commission (FCC) is also a high priority, Notebaert said.
Qwest last week filed an application with the FCC for authority to provide long-distance phone service in five western US states and said it plans to file similar applications for the nine other states where it provides local phone services.
Qwest, like many of its competitors, is beset with financial problems. Credit rating agencies have downgraded the company's rating and its accounting practices are being investigated by the US Securities and Exchange Commission. Qwest is about $26.2bn (£17.7bn) in debt.
"This management change does not reflect a change in Qwest strategy or operations," said Frank Popoff, a Qwest board member. "Sale of non-strategic assets and associated debt reduction is proceeding as planned."
Nacchio's replacement does not come as a surprise, especially after the high-profile departure of Bernard Ebbers at WorldCom in late April, said Maribel Dolinov, a senior telecom analyst with Forrester Research.
"Service providers are desperately trying to gain credibility in the financial markets. One way to do that is change top management," she said, adding that she expects more executives to leave.
Notebaert's plan to meet with customers is key for Qwest, although the changes that are needed at Qwest - reduction of debt, staff, and capital expenditure - are not customer issues, Dolinov said.
"Most critical for all service providers, in a market where there is not the demand that they expected, is to maintain the customers they have. Every customer in the telecom environment is scared and looking at their options. Do they stay with their provider or do they change?" she said.
Tellabs chairman Michael Birck will take Notebaert's place as chief executive officer and president of the company.