After college, Malone entered the banking industry. He was president of the First National Bank of Dothan, which was one of several banks that merged to become SouthTrust in 1972. Malone was elected President of SouthTrust Corporation, and in 1980 he was elected Chairman of the Board. He moved to Birmingham, where the bank was headquartered. He served as President, Chairman and CEO until 2004, when he successfully brokered a deal for the bank to be acquired by Charlotte, N.C.-based Wachovia Bank. He stayed on as a member of Wachovia's board of directors until 2007.
Malone is married to the former Ocllo Smith. He and his wife have six children: Wallace Davis Malone III, Frances R. Joy, Catherine M. Wilson, S. Lee Robertson, Alyson D. Malone, and Ocllo R. Mason.