Leavenworth era hijo del general de brigada Henry Leavenworth y su esposa Elizabeth Eunice Morrison. Nació el 29 de marzo de 1807 en Danville, Vermont . Se graduó de la clase de West Point de 1830.
Después de graduarse, fue comisionado como segundo teniente en el 4º de Infantería , conocido como los "Rocky Mountain Rangers", con base cerca de Denver, Colorado , que protegía la frontera contra bandidos y merodeadores indios.
Leavenworth se casó con Elvira Caroline Clark, hija de Festus Clark, de Sackett's Harbour, Nueva York , el 12 de junio de 1832, y tuvieron cuatro hijos y cuatro hijas entre 1833 y 1853. Renunció al ejército en 1836 para pasar más tiempo con su familia. .
Leavenworth fue un ingeniero civil activo en el oeste, con una práctica privada con sede en Chicago, Illinois , durante 22 años. También trabajó como comerciante de madera en Wisconsin.
El 17 de febrero de 1862, después del estallido de la Guerra Civil estadounidense , fue nombrado coronel de los voluntarios y recibió el mando del 2º Regimiento de Infantería de Colorado . Una vez más fue asignado a los "Rocky Mountain Rangers" en los que ahora tenía la responsabilidad adicional de protegerse contra la acción de los simpatizantes confederados . Fue dado de baja honorablemente el 26 de septiembre de 1863.
En 1864, el Ejército nombró a Leavenworth como agente indio de los Cheyenne , Kiowa y Comanche del Sur , en representación del gobierno de los Estados Unidos en sus intentos de mantener la paz con las tribus. Fue responsable de una serie de liberaciones cautivas de rehenes tomados por las tribus.