ממשלת תימן נאבקת לשמור על המומנטום נגד אל-קאעידה בחצי האי ערב (AQAP), תוך כדי עמידה באתגרים רבים שמציבים גורמי משטר לשעבר, פורשים דרומיים, מורדים חות'ים (פלג של השיעים) ויריבים שבטיים. כך אומרת מחלקת המדינה של ארה"ב בדוח על הטרור בשנת 2013.
תהליכי הארגון מחדש של הצבא וכוחות הביטחון, דבר שנועד לאחד את מבנה הפיקוד של הכוחות המזוינים, לא הושלם. הדבר גורם למצב של יחידות קדמיות בעלות אימונים וציוד דלים, שלא יכולים להתמודד עם האיום של AQAP. הצבא התימני לא ביצע פעולות גדולות נגד הטרור בשנת 2013. במקום זאת, הם הניחו יציבות הגנתית, תוך הסתמכות על מבצעים בקנה מידה קטן שכוללות פשיטות והתקפות אוויריות, בתגובה להתקפות AQAP.
הארגון מנצל עיכובים בארגון מחדש של הצבא, שנובע מהמעבר הפוליטי בתימן, ומתמקד במתקנים צבאיים וביטחוניים באזורים רבים, בנוסף להתנקשויות וחטיפות גורמי צבא, ביטחון ומודיעין. הארגון פעל גם נגד מליציות שבטיות התומכות בממשלה, בעקבות תפקידן בהנסת הארגון מדרום תימן בשנת 2012.
למרות אתגרים אלו, ממשלת תימן נשארה שותפה חזקה של ארה"ב בלוחמה בטרור. נשיא תימן, עבד אל-ראב מנסור אל-האדי, תמך במבצעים של ארה"ב ללוחמה בטרור בתימן, ועודד שיתוף פעולה בין צבא ארה"ב ומפקדת הכוחות המיוחדים בתימן ומשרד הלוחמה בטרור. צבא ארה"ב אימן יחידות לוחמה בטרור מתימן, במאמץ לבנות מחדש את משרד הביטחון.
התנקשויות ומכוניות תופת פקידים בממשלת תימן האשימו את חברי התנועה הדרומית (South Yemen Movement. תנועה שמבקשת להיבדל מתימן), בביצוע פעולות נגד הממשלה. גורמי ביטחון בכירים העלו את האפשרות שאירן מסייעת להם, כמו שהיא מסייעת לקבוצות אחרות בתימן, כדי ללבות את האלימות העדתית.
מבחינת אירועי טרור בתימן בשנת 2013, AQAP וארגונים אחרים שמזוהים איתו, ביצעו מאות פיגועים ברחבי תימן, כולל פיגועי התאבדות, פיצוץ מכוניות תופת, מארבים, חטיפות והתנקשויות ממוקדות על-ידי חמושים על אופנועים.
ב-10 בינואר התנקשו חמושים אלמונים בפוליטיקאי מקומי, ששימש כמתווך בין הממשלה לבין AQAP. ב-27 באפריל תקפו חמושים שמזוהים עם AQAP מחסום בעיר ראדה והרגו חמישה חיילים. ב-20 בספטמבר פוצצו חמושים שמזוהים עם AQAP שתי מכוניות תופת ליד בסיס צבאי במחוז שבוה ורצחו 21 חיילים.
ב-30בספטמבר תקפו חמושים של AQAP תקפו בסיס צבאי במחוז חצרמוות. האירוע החל כאשר מחבל מתאבד פוצץ עצמו בכניסה לבסיס. לאחר מכן, מספר חמושים במדי הצבא פתחו בירי והרגו עשרה חיילים.
ב-5 בדצמבר ביצעו חמושים מטעם AQAP התקפה משולבת על מטה משרד הביטחון בעיר צנעא. שני מחבלים מתאבדים השתתפו בפיגוע, כאשר הראשון פוצץ את עצמו בכניסה למתחם, והשני בכניסה לבית חולים. חמושים במדי צבא נכנסו לבית החולים ופתחו באש. בפיגוע נהרגו 57 אנשים ומאות נפצעו. מפקד AQAP התנצל לאחר מכן על ההתקפה על בית החולים, בעקבות זעם ציבורי.
יכולת גילוי מוגבלת מבחינת אכיפת החוק, ב-17 בספטמבר אישר הפרלמנט התימני תיקון לחקיקה נגד טרור משנת 2008. התיקון יאפשר מעצר חשודים ומתן גזר דין על מעורבות במספר אירועי טרור. בשנת 2013 נעצרו עשרות חשודים בטרור, אך רבים מהם קיבלו עונשים קלים בשל המסגרת המשפטית הנוכחית.
יחידות האכיפה הציגו יכולת מוגבלת לגילוי, הרתעה ויכולת תגובה על אירועי טרור. היה שיתוף פעולה בין-משרדי בנושא, אך הוא היה מוגבל. חולשת מערכת המשפט בנוגע לעבירות טרור גורמת לתסכול בקרב רשויות אכיפת החוק. תימן הפעילה סינון ביומטרי וגאוגרפי ב-26 נקודות כניסה למדינה, באמצעות אימוץ התוכנית לסיכול טרור.
מבחינת שיתופי פעולה בנוגע ללוחמה בטרור, תימן משתתפת ומקבלת ייעוץ ממועצת שיתוף הפעולה במפרץ, ארה"ב וירדן. באפריל 2013 תימן אירחה לראשונה את פורום הלוחמה בטרור של מפרץ עדן.
מבחינת התמודדות עם הקצנה לאלימות וקיצונים אלימים, האדי ובכירים נוספים הדגישו את חשיבות המאבק בטרור, בהתייחסות לתנאים שהמחבלים מנצלים. ממשלת תימן הביעה תמיכה בשיקום ושילוב מחדש של קיצונים אלימים. באוגוסט 2013 הוקמה קבוצת היגוי ביחד עם ארה"ב לקידום רעיון זה.