In 1940, he entered the School of Architecture at Howard University, but interrupted his studies to serve as a second lieutenant in the U.S. Army during World War II.

He was a member of the U.S. Army's African-American 92nd Infantry Division and served in Italy, receiving three combat ribbons and the Purple Heart.

[3] He entered Harvard University's Graduate School of Design in 1951, studying under Walter Gropius, and received his master's degree in architecture in 1952.

[3][6][7] Madison briefly taught architectural design and site planning at Howard University as an assistant professor,[1] before being awarded a Fulbright Scholarship to study abroad.

[citation needed] In 1965 the firm was selected to design the U.S. Embassy Office Building in Dakar, Senegal, West Africa.

[1][15] Madison reports being "very close" to Coretta Scott, later the wife of Martin Luther King Jr., when he first returned from his war service,[1] and was once engaged to her.