Halstead wuchs in Willseyville auf und war nach ihrem Abschluss an der Candor High School die erste Person aus ihrer Stadt, die 1977 die United States Military Academy in West Point besuchte. 1981 erhielt sie dort einen Bachelor of Science in Ingenieurwissenschaften. Nach ihrem Abschluss wurde sie dem Artilleriekorps zugeteilt. Noch während ihrer Zeit bei der Armee setzte sie ihre Ausbildung fort und erlangte 1993 einen Master-Abschluss in fortgeschrittenen Militärstudien am Command and General Staff College in Fort Leavenworth, Kansas. 2000 erwarb sie einen Master-Abschluss in National Resource Strategy am Industrial College of the Armed Forces der National Defense University in Fort McNair.[2]
In Afghanistan diente Halstead während der Operation Enduring Freedom als Logistikstabsoffizierin für die Coalition Task Force Afghanistan. 2004 wurde sie zum Brigadegeneral befördert und war damit die erste Absolventin der United States Military Academy, die den Rang eines Generals erreichte. Sie übernahm als erste Frau in der US-Geschichte das Kommando im Kampf auf strategischer Ebene, als sie zum Senior Commanding General für Logistik im Irak befördert wurde. In dieser Funktion war sie für die Führung von über 200 multidisziplinären Einheiten verantwortlich, die auf 55 Stützpunkte verteilt waren und über 250.000 im Irak stationierte Soldaten mit Versorgung, Wartung, Transport und Vertriebsdiensten unterstützten.[3]
2006 wurde Halstead die erste weibliche Chefin der Artillerie und kommandierende Generalin des Artilleriezentrums und der Schulen der Armee.
Halstead ging im Juni 2008 in den Ruhestand. Von 2009 bis 2010 war sie als Kommissarin für die Presidential Commission on Military Leadership Diversity tätig. 2010 gründete sie das Beratungsunternehmen STEADFAST Leadership, das sich auf die Ausbildung von Führungskräften und die Entwicklung von Teams spezialisiert hat, und wurde deren CEO. Sie ist außerdem Sprecherin der Foundation of Chiropractic Progress, die sich für die Gesundheit und Ressourcen von Veteranen einsetzt. Darüber hinaus ist sie Mitglied des Beirats der Thayer Leader Development Group in West Point und Beraterin des Gordian Institute.[4]