At West Point, Brooks was the academy's first African-American Cadet First Captain, the highest position (Cadet Brigade Commander) a cadet can hold, an appointment that brought much public visibility at an early age in life. He graduated from West Point in 1980. After graduating, Brooks served in South Korea and Kosovo among other places. In Kosovo, he concurrently served as the deputy commander of the U.S. force in Kosovo (Task Force Falcon) and as commander of the 1st Brigade, 3rd Infantry Division based at Fort Stewart in Georgia. From that position he moved to the Joint Chiefs of Staff at the Pentagon. While serving there he was temporarily assigned to be Deputy Director of Operations at United States Central Command (CENTCOM). Returning to the Pentagon and the Joint Staff in April 2003, he became the Lead Strategic Planner for the Global War on Terrorism working closely with the CIA, the Departments of State, Treasury and Justice, the FBI and the military's United States Special Operations Command (SOCOM).