While a colonel, Brooke was ordered in 1823, along with James Gadsden, to establish a military presence in the vicinity of Tampa Bay, in the newly acquired Florida Territory.
The site was marked by a huge hickory tree atop an ancient Indian mound most likely built by the Tocobaga culture centuries before.
Brooke directed his troops to clear the area for the construction of a wooden log fort and support buildings.
On June 10, 1846, he was appointed commander of the Western Division of the United States Army, taking over for General Edmund P. Gaines.
He was responsible for forwarding reinforcements and supplies to the field armies of generals Zachary Taylor and Winfield Scott in Mexico and operated out of headquarters in New Orleans.