The Jindal administration canceled the nearly $200 million contract with Maryland-based CNSI last week after details leaked of a federal grand jury subpoena involving the contract award.
The governor's office announced Greenstein's decision, saying his resignation from the $236,000-a-year post takes effect May 1. Jindal spokesman Kyle Plotkin said the governor didn't ask Greenstein to leave his position as secretary of the Department of Health and Hospitals.
Greenstein offered no explanation in his two-page resignation letter, instead recounting his accomplishments and thanking the governor. He didn't respond to messages Friday seeking further comment.
"This state's gracious people and generous culture have left a permanent and meaningful impact on the lives of my family and me. I am grateful for our time here and I will forever remember this period of our lives with fondness and pride," he wrote to Jindal.
When the Medicaid contract was awarded two years ago, Greenstein denied any involvement in the selection.
But he acknowledged under questioning from lawmakers in his 2011 confirmation hearing that a change he pushed in the bid solicitation made CNSI eligible for the Medicaid contract. He also met with a top CNSI official within days of taking the health secretary's job.
Greenstein worked for CNSI from 2005 to 2006.
The state attorney general's office has said the 10-year contract for Medicaid claims processing and bill payment was improperly handled, and it is conducting its own criminal investigation into the contract award.
David Caldwell, head of the attorney general's public corruption unit, said there was inappropriate contact between CNSI and DHH employees, among other issues.
Greenstein's resignation leaves Jindal without the chief defender of his opposition to the Medicaid expansion under the federal health care law, as state lawmakers are pushing against the rejection.
It also removes from ongoing negotiations the architect of the Jindal administration's efforts to privatize the LSU-run public hospitals that care for the poor and uninsured and that train many of Louisiana's medical students.
In a statement, Jindal praised Greenstein's tenure at the health department, during which he oversaw the privatization of many state-run health facilities and shifted much of the Medicaid program to private managed care.
"Bruce has successfully led one of the largest transformations of our state's health care delivery system," Jindal said.
Greenstein started work at DHH in September 2010.
Before taking the helm of Louisiana's largest state agency, he was a health economist and managing director of worldwide health for Microsoft Corp. Other past jobs included work for the federal Centers for Medicare and Medicaid Services and health policy analysis for the Government Accountability Office, Congress' investigative arm.
When Greenstein leaves, his deputy secretary, Kathy Kliebert, will serve as interim secretary of the department and will receive the same annual salary Greenstein was paid, according to Jindal's office.
Greenstein hadn't been seen at public events since news of the Baton Rouge-based federal grand jury probe. Lawmakers were irritated that the health secretary skipped his agency's budget hearing earlier this week.
On Friday, a DHH spokeswoman referred all questions about Greenstein's resignation to the governor's office.
CNSI, which was supposed to take over the Medicaid work next year, is challenging the termination of its contract by the state. CNSI beat three other companies for the work, but critics said the company underestimated the true cost of the job and made incorrect assumptions to win the bid.