DPD, już jako asystent szefa sztabu. W 1995 został przydzielony do sztabu misji ONZ na Haiti jako szef operacji wojskowych w trakcie operacji Uphold Democracy, a następnie na dwa lata został dowódcą 1 Brygady 82 Dywizji Powietrznodesantowej. Gdy przebywał na tym stanowisku, Tom Clancy w książce Airborne opisał cykl treningowy brygady Petraeusa, który ta odbyła w Fort Polk’s Joint Readiness Training Center. Od 1997 do 1999 Petraeus służył w Pentagonie jako asystent Dyrektora Połączonych Sztabów, a następnie Przewodniczącego Kolegium Połączonych Szefów Sztabów, gen. Henry’ego Sheltona. W 1999, będąc już w randze generała brygady (ang. Brigadier General), Petraeus powrócił do 82 DPD jako asystent jej dowódcy ds. operacji, a przez krótko piastował nawet stanowisko samego dowódcy. W tym okresie dywizja została wysłana do Kuwejtu w ramach operacji Desert Spring – trwającej od czasu wojny w Zatoce Perskiej rotacji sił w tym kraju.

Z 82 DPD przeniesiono go na stanowisko szefa Sztabu XVIII Korpusu Powietrznodesantowego w Fort Bragg. W 2000 po raz drugi został ciężko ranny, kiedy podczas cywilnego skoku spadochronowego jego spadochron zapadł się osiemnaście metrów nad ziemią;