Чарлс Болдън започва военната си служба като младши лейтенант в USMC през 1968 г. Преминава допълнително обучение за морски пилот в Пенсакола, Флорида и Кингсвил, Тексас. Завършва курса с отличие през май 1970 г. От юни 1972 до юни 1973 г. участва в бойните действия във Виетнам. Извършва 100 бойни полета над Виетнам, Лаос и Камбоджа на самолет А-6 Интрюдър. През 1979 г. завършва школа за тест пилоти. През кариерата си има повече от 6000 полетни часа на реактивни самолети. От 27 юни 1994 г. е комендант на Военноморската академия на САЩ. През юли 1997 г. е произведен в чин бригаден генерал и назначен за командир на I Експедиционно съединение на USMC. От февруари до юни 1998 г. е командващ операция „Гръм в пустинята“ (на английски: Operation Desert Thunder) в Кувейт. През юли същата година е произведен в чин генерал-майор и назначен за командир на Експедиционните сили на САЩ в Япония. От 9 август 2000 до края на август 2002 г. е командир на 3-то авиокрило на USMC. През август 2004 г. напуска армията и се връща на служба в НАСА.
Служба в НАСА
На 29 май 1980 г. Ч. Болдън е избран като астронавт от НАСА, Астронавтска група №9. През август 1981 г. завършва успешно курса на обучение. Той е ветеран от четири космически полета и има 680 часа в космоса.
