In 1973, McKenzie became deputy superintendent of District of Columbia Public Schools.[1] In 1974, she moved to Maryland and was hired as the assistant superintendent of Montgomery County Public Schools and also worked as schoolteacher.[1][2] While working for the U.S. Department of Education as Deputy Assistant Secretary in the Office of School Improvement, she managed fifteen federal educational discretionary programs and initiatives.[1] McKenzie also served as the United States delegate to the UNESCO General Conference in Yugoslavia.[2]
In 1981, McKenzie returned to Washington, D.C. as the Superintendent of the District of Columbia Public Schools, succeeding Vincent E. Reed, and as Chief State School Officer.[1] In her capacity as Chief State School Officer, she oversaw the country's twenty-first-largest school system, managing 89,000 students, 13,000 employees, and operating with a $400 million budget.[1] As superintendent, she expanded curriculum reforms, emphasized a return to "competency-based curriculum", and was credited with spurring an upturn in elementary school achievement.[1] She also started a summer school initiative to advance students to the next grade and made alliances with local companies, trade associations, and foundations to help improve instructional programs, school-system management, and personnel training programs.[1] McKenzie resigned from office in 1988 to start The McKenzie Group, an educational consulting firm focusing on urban schools.[1] She served as The McKenzie Group president until 1997, when she became the company's chairwoman.[2]
In 1992, she became the first African-American elected board member of the Marriott Corporation and was the first woman to serve on the board who was not a member of the Marriott family.[1] She also served on the board of Pepco, Acacia Life Insurance Company, CareFirst BlueCross BlueShield, Johns Hopkins Leadership Development Program, the White House Historical Association, and the National Geographic Society's Education Foundation.[1][2] She served on the board of trustees of Howard University for twenty-one years and was a lecturer at American University's Graduate School of Education.[4][2]