לאחר מכן, גאגא ורקדניה מוצגים ברצף בשחור-לבן במדיהם הצבאיים בביצוע מחווה המוקדשת לכוריאוגרף המנוח בוב פוסה, שזכה בפרס אוסקר על בימויו של הגרסה הקולנועית לקברט. גאגא נראית עם שיער בלונדיני ותלבושת דומה לאחת מתלבושות ההופעה של ליזה מינלי. הסרטון עובר לסצנה שגאגא לובשת חזייה המצוידת ברובי AR-15 ורקדניה מבצעים שגרת ריקודים נוספת. לאחר מכן היא מוצגת במועדון ריק, בסצנות מלחמה שפורצות מבצבצות והחייל הבודד מופיע שוב. הסרטון מסתיים בה לבושה כנזירה, ופניה נשרפים כלפי חוץ. קליין הסביר כי הסרטון היה, "על רצונה של אישה להחיות אהבה מתה ואשר לא יכולה להתמודד עם האכזריות של מצבה הנוכחי. הכאב לחיות ללא אהבתך האמיתית".
קבלה.
ג'יימס מונטגומרי מערוץ MTV העיר כי "גאגא יצרה עולם שאף על פי שהוא מעיק, נראה גם נהדר". בקטע נפרד מונטגומרי הוסיפה כי "ייתכן שהיא סוף סוף הגיעה לנקודה בקריירה שבה אפילו היא לא יכולה להתגבר על עצמה". דניאל קרפס ממגזין הרולינג סטון כינה את הסרטון "אפוס קולנועי". בראד ווט ממגזין אנטרטיינמנט ויקלי, אהב את הסרטון אך עם זאת, לא היה לו מושג מה קורה בו, "אני לא יכול לחכות לשמוע את ליידי גאגא מסבירה על הקליפ האחרון שלה, "Alejandro" בעיקר כי אחרי שצפיתי בו (פעמיים!), אין לי שום מושג מה קורה". אנתוני בניניו מהעיתון ניו יורק דיילי ניוז הרגיש כי "הקליפ החדש של גאגא הוא הלם... מלא מלא דימויי סאדומזוכיזם מונחים במיטה שגורמים לו להיראות כמו התשובה הרכה של מטריקס. רנדל רוברטס מהעיתון לוס אנג'לס טיימס אמר כי "הקליפ מחזק את התפיסה שאף אחד לא מבין את התכנסות הדימוי והמוזיקה כרגע טוב יותר מגאגא". ג'ד גוטליב מהעיתון "Boston Herald" אמר כי "את העלילה של הקליפ קשה לפענח, אבל ברור שזה לא סיפור שמסתיים באושר ועושר". ג'ן דוס מהעיתון הקנדי "National Post" אמר כי "הסרטון החדש של גאגא ל-"Alejandro" בהחלט מביא את השיגעון שכולנו ציפינו ממנה. זה כמו הומאז בן 8+ דקות למדונה - עם כמה מדי נאצים הומוסקסואליים שנזרקו לשם טוב". איימי אודל מהמגזין ניו יורק אמרה כי תלבושות הסרטון לא היו אינטנסיביות כמו אלה של "Bad Romance" או "Telephone". נייט ג'ונס ממגזין טיים לא אהב את השיר, אך הרגיש שהקליפ "נראה פנטסטי... הכדאיות המודעת עצמית של גאגא ושל הבמאי סטיבן קליין עובדת כאן". ג'ניפר קאדי מהערוץ E! אהבה את הקליפ, אך לא חשב שהוא טוב כמו עבודתה הקודמת של גאגא.
הסרטון הושווה בכבדות גם ליצירות של אמני פופ משנות השמונים כמו מדונה וג'נט ג'קסון. המבקרת מוניקה הררה ראתה בסרטון הכלאה של "Like a Prayer" של מדונה ושל "Rhythm Nation" של ג'נט ג'קסון. קייל אנדרסון מערוץ MTV מצא התייחסויות לסרטה של מדונה משנת 1996, אוויטה, ולקליפים לשיריה "Human Nature","Like a Prayer" ו-"Vogue". מגזין הרולינג סטון השווה את הצילום השחור-לבן של הסרטון לזה של "Vogue", והבחין בכמה רמזים "לא כל כך עדינים" כלפי "Like a Prayer". המגזין האמין ש-"Alejandro" דומה כל כך לעבודתה של מדונה מכיוון שהבמאי סטיבן קליין עבד בשיתוף פעולה הדוק עם מדונה לפני שצילם את "Alejandro". דבון תומאס מהרשת "CBS News" אמר כי "האיסונות של מדונה מתרוממים בקליפ". הוא ציין ששיערה הקצר, הקצוץ והבלייזר השחור של גאגא "על רקע הלך הרוח הפוסט-תעשייתי של הקליפ "Alejandro" היה דומה לקליפ "Express Yourself" משנת 1989 וחזיית הרובים של גאגא בקליפ דומה גם כן לחזיית החרוט אשר מדונה לבשה בקליפ עבור "Vogue". הוא גם השווה את הסרטון לסבב ההופעות של מדונה, "Blond Ambition World Tour" משנת 1990 באומרו כי "הסרטון הזה הוא מכתב אהבה חזותי למדונה". מגזין ניו יורק אמר כי הסרטון "משמח" את מדונה. ג'יימס מונטגומרי מחדשות MTV הגן על גאגא נגד ההשוואות של מדונה באומרו, "רק כדי להגיד, אה, כי זה בשחור לבן ויש לה תספורת קצרה בשלב מסוים, זו מדונה, זה סוג של מכירת ראיה קצרה". הוא גם אמר שהקליפ של "Alejandro" הוא "לא הסרטון הסרטון הטוב ביותר בעולם". במאמרה בסאנדיי טיימס כתבה קמיל פגליה "גאגא לוותה כל כך הרבה ממדונה (כמו בסרטון האחרון שלה - "Alejandro") שיש לשאול, באיזו נקודה הופך הומאז 'לגניבה?".
דימוים דתיים.
"Alejandro" יצר סערה תקשורתית לאחר פרסום הקליפ שלו בגלל השימוש הקיים בו של דימויים דתיים. אחת הסצנות המדוברות ביותר בסרטון הייתה כשגאגא, לבושה בתלבושת נזירה לטקס, בלעה חרוזי שרשרת צלב. הליגה הקתולית מתחה ביקורת על הסרטון על השימוש בו בדימויים דתיים והאשימה את גאגא ב-"משחק חתולי דמוי מדונה". מוניקה הררה אמרה על המהומה כי, "Alejandro" יוצר מחלוקת דתית באותו אופן שעשה פעם הקליפ של "Like a Prayer" של מדונה, תוך כדי שהוא מערבב דימויים קתוליים כמו חרוזי מחרוזת וגלימות של נזירות עם רמזים מיניים". בראיון לערוץ MTV, הסביר קליין שהסמליות הדתית לא נועדה לסמן שום דבר שלילי, אלא לייצג את הקרב של גאגא בין הכוחות האפלים והקלים יותר. כך שבסוף הקליפ היא מצטיירת שוב בלבוש הנזירה שלה. קליין הוסיף כי המשמעות שמאחורי הקטע בו פיה ועיניה נעלמות בקליפ הייתה "מכיוון שהיא מושכת את חושיה מעולם הרשע והולכת פנימה לעבר תפילה והתבוננות". הוא הוסיף כי הסצנה שבה גאגא בולעת את חרוזי המחרוזת היא "מעשה התיאופגיה שלה, הרצון לצרוך את גופו של אלוהים, המחרוזת היא סמלית לקודש".
מבקרים רבים הסכימו שהדימויים הדתיים הם מהלך מחושב של גאגא ליצירת מחלוקת. סיימון ווקסיק לוינסון מהמגזין אנטרטיינמנט ויקלי חש שהמהלך מחושב ואמר: "גאגא רוצה לפגוע באנשים. היא פרובוקטורית. גאגא כנראה תתאכזב אם אף אחד לא ייעלב מהקליפ האחרון שלה. היא עושה את הדברים האלה מסיבה כלשהי". הוא לא חשב שהסיכונים מקוריים מאוד או מרגשים כמו אלה שב-"Telephone" והוסיף, "הסיכונים שהיא לקחה... היו יעדים קלים יותר... היו שם קצת, היא עשתה את זה". אמר. ג'ון קרמניקה מהעיתון הניו יורק טיימס חשב שהמחלוקת היא הניסיון של גאגא לתפוס את כס המלכות של תואר "מלכת הפופ". הוא אמר, "אני בטוח שהיא הייתה אומרת שהיא אוהבת את מדונה... אבל אני גם חושב שהיא אומרת, "תואר מלכת הפופ הוא שלי" או "אני רוצחת אותך בסגנון שלי. למדתי את זה. אני יודעת לעשות את זה... ותראה כמה אני עושה את זה ללא דופי". עם זאת, הוא הרגיש שהדימויים הדתיים ברורים ועצלנים, "אפילו הפרובוקציה הגרועה ביותר שלה תצליח. היא קיבלה את מה שרצתה". זמרת הפופ קייטי פרי כתבה בחשבון הטוויטר שלה כי, "שימוש בחילול השם כבידור הוא זול כמו קומיקאית שמספרת בדיחות נפיחות". באתר הפינגטון פוסט התברר כי גאגא אמנם לא הוזכר ישירות על ידי שמה בציוצה של פרי, אך נאמר כי זה היה מכוון בהחלט כלפי עבודתה של גאגא. בראיון בתחנת רדיו, אמרה פרי כי הציוץ אינו נוגע אך ורק לגאגא, וקבעה כי הוא מבוסס על השקפותיה האישיות כלפי הדת.
הופעות קידום.
גאגא ביצעה את "Alejandro" במהלך השנים 2009–2011 בסבב ההופעות "The Monster Ball Tour". הוא היה השיר הרביעי ברשימת ההשמעה בלג הצפון אמריקאי של הסבב. עם זאת, בלגים האירופים והבריטים של הסבב, השיר בוצע לקראת סוף המופע. ההופעה החיה הראתה את גאגא לובשת בגד גוף כסוף ואז נישאת על ידי מפשעתה על ידי אחד הרקדנים הגברים שלה ומורדת על ידי רקדן גברי נוסף, ובמהלכו, עוסקת בשלישייה איתם. ג'רמי אדמס ממגזין הרולינג סטון הגיב כי ההופעה הייתה "אחד מכמה רגעים שהעניקו להורים בקהל התפעלות". ג'ים הרינגטון מסן חוזה מרקורי ניוז השווה את הביצועים של גאגא לשיר לזה של רקדנית ארוטית. בגרסה השנייה של סבב ההופעות גאגא התרחצה במזרקה על הבמה שהייתה העתק של הנוכחת בסנטרל פארק בניו יורק.
ב-20 באפריל 2010, גאגא ביצעה את השיר בהשקת הקרן "Mac AIDS Fund" בטוקיו, שם לבשה שמלת תחרה. היא נכנסה לבמה בתהלוכה בהשראת חתונה יפנית, וכשהאורות התעמעמו, היא התיישבה ליד הפסנתר שלה על הבמה המסתובבת וביצעה את "Speechless", ואחריו את "Alejandro" אשר במהלכו, אחד הרקדנים שלה, נראה היה מכוסה באבקת טלק. גאגא הופיעה יחד עם שילוב של "Bad Romance" ו-"Alejandro" בעונה התשיעית של אמריקן איידול ב-28 באפריל 2010. הופעתה עלתה לאוויר בפרק 5 במאי 2010. ההופעה החלה בכך שגאגא ניגנה בפסנתר בקטע מואט של "Bad Romance". היא הייתה לבושה בתלבושת שחורה חושפנית אך מצועפת, עטתה שכמייה והוקפה ברקדנים ללא חולצה. באמצע ההופעה היא השילה את שכמייה והחלה להתפתל על הרצפה. בפינה אחת של הבמה, מתוך פסלה של מריה הבתולה נשפכו להבות מראשו, כשגאגא שרה את הפזמון. ערפל מילא את הבמה, כשגאגא ורקדניותיה ביצעו שגרת ריקודים אנרגטית. לוצ'ינה פישר מחדשות "ABC" כינתה זאת כ-"הופעה מצועפת נוטפת סקס וכינורות" והוסיפה כי "גאגא עושה את מיטב ההתרשמותה של מדונה בעבר". ב-9 ביולי 2010 ביצעה את השיר השיר בתוכנית הבוקר, "Today", שם שרה אותו בבמה מחוץ לאולפן. במאי 2011 ביצעה גאגא את השיר במהלך סוף השבוע הגדול של רדיו 1 בקרלייל, קומבריה.