מה הניע ליטאים רבים כל כך לקחת חלק פעיל, מיוזמתם, בחיסול היהודים שחיו בקרבם שנים רבות בשכנות טובה יחסית והיוו חלק נכבד באוכלוסייה?
מסע עם האויב מתאר מסע של שני אנשים שמבקשים לרדת לחקר האמת בשאלת רצח יהודי ליטא בתקופת השואה; האחד צייד נאצים יהודי, השנייה סופרת ליטאית מצליחה. המסע הזה ישפיע על כל אחד מהם באופן דרמטי.
רוטה ונאגייטה יצאה למסע לאחר שהתברר לה שכמה מקרובי משפחתה לקחו חלק פעיל בתהליך רצח היהודים במקומות שונים בתקופת השואה וסייעו גם בהסתרת חלקם של משתפי פעולה בפשעי שואה.
ד"ר אפרים זורוף, צייד הנאצים הראשי של מרכז ויזנטל, עמל במשך שנים ארוכות על מנת להביא למשפט פושעי מלחמה ליטאים ולגרום לשלטונות בליטא לחשוף את האמת על אודות מה שאירע במדינה בזמן השואה. העובדה שסבו וסבתו מצד אמו נולדו בליטא ושהוא נקרא על שמו של דוד-רבא שנרצח עם משפחתו בווילנה בעזרתם הפעילה של ליטאים העניקה למסע שלו נופך אישי במיוחד.
מסע עם האויב חושף את התפקיד המשמעותי ביותר שמילאו מנהיגים פוליטיים והממסד הליטאי בביצוע הפתרון הסופי; בד בבד המחברים אינם חוששים לדון במניעים שהביאו אלפי ליטאים פשוטים לרצוח את שכניהם היהודים.
תוך שימוש בחומרים ליטאיים בלבד: ספרים שכתבו היסטוריונים ליטאים; עדויות של רוצחים; ראיונות עם עדי ראייה ותושבים מקומיים, כולל כאלה החיים עד היום בקרבת אתרי הרציחות ההמוניות, מנתחים ונאגייטה וזורוף את העדויות ומתווכחים ביניהם על פרשנותן, בעודם תרים את הארץ לאורכה ולרוחבה ומבקרים ביותר מ-30 אתרים שבהם נרצחו יהודי ליטא, כ-212 אלף במספר מתוך 220 אלף היהודים שחיו בה טרם הכיבוש הנאצי. זהו אחוז הנרצחים הגבוה ביותר בקרב הקהילות היהודיות הגדולות במהלך השואה.