התייחסו לקטע הבא ואז ענו על השאלה שאחריו באותה שפה כמו הקטע:  Passage: עם שם חדש ומועדון חדש, הלהקה הוציאה את האלבום השני שלה, New American Gospel, בספטמבר 2000. פטריק קנדי מ-Allmusic השווה את הלהקה לפנטרה ואמר: "הסימנים החיוניים של הפוסט-פנטרה מטאל נמצאים בשפע באלבום הפתיחה של Lamb of God. "הג'ונגל האמריקאי החדש מספק עץ אלון עוצמתי שעליו נשמרת האמונה של המתאל האמריקאי הקשוח, ובאופן אפקטיבי מגשר בין ההתעקשות של שנות ה-90 על טכניקה של סמל התרגיל וההתמקדות הנחושה של בית הספר הישן בבניית ריף". כריס אדלר אמר: "זה תקליט קלאסי. היו לנו את כל האלמנטים שהתאחדו כדי ליצור את אחד התקליטים הכבדים, אך החולפים ביותר בקריירה שלנו. זה היה קשה להכיל אותנו - אפילו לא הבנו באותו הזמן מה יצרנו. "להקת Lamb of God יצאו לסיבוב הופעות במשך שנתיים לפני ששיחררו את אלבום האולפן השלישי שלהם, As the Palaces Burn, ב-6 במאי 2003. קירק מילר מ"רולינג סטון" נתן לאלבום שלושה מתוך חמישה כוכבים, וכתב כי "בניגוד לרבים מהזמנים שלהם, שהשפיעו על סליפנוט, Lamb of God מספקת תקיפה מתוחכמת של מתכת". האלבום נבחר לאלבום מספר אחד של 2003 על ידי מגזין Revolver ו- Metal Hammer. הלהקה הייתה חלק מהסבב ההופעות הראשון של ה-Headbangers Ball, שבו הם הקליטו DVD הכולל הופעות חיות וסרט תיעודי, שכותרתו Terror and Hubris. ה-DVD היה הצלחה, והגיע למקום ה-31 במצעד של בילבורד Top Music Videos.  שאלה: מתי יצא האלבום הראשון שלהם תחת שם חדש?
ספטמבר 2000