כתובת עברית קדומה מצויה מתחת לקשת רובינסון ומצטטת (לא במדויק) מדברי ישעיהו הנביא () את המילים "וראיתם ושש לבכם ועצמותם כדשא". בין הנוסח הזה לנוסח המסורה יש שני שינויים חשובים: "ועצמותם" במקום "ועצמותיכם", וחסרונה של המילה "תפרחנה" אחרי "כדשא". כתובת זו נחשפה בחפירות בידי בנימין מזר, והוא תארכה למאה ה-4, וייחסה ליהודים שקיוו לבניין בית המקדש השלישי, בעקבות תמיכת הקיסר יוליאנוס הכופר בבנייתו. מאוחר יותר חפרו במפלס שמתחת לכתובת רוני רייך ויעקב ביליג וגילו בית קברות, ככל הנראה של נוצרים. אחת מהשערותיהם היא שהכתובת מתייחסת אל נקברים אלה, ושהשינוי בנוסח הפסוק נעשה בכוונה תחילה - כלעג לעצמות הגויים.
ברחבות הכותל המערבי מצויות, בנדבכים שמעל לראשי המתפללים, כתובות רבות המאזכרות שמות עבריים, ככל הנראה של עולי הרגל עצמם שבכך ביקשו להנציח את שמם על גבי האבנים הקדושות. כתובות אלו נחרתו על אבנים שהיו בעבר בגובה המתפללים, אך בשל הנמכת מפלס הרחבה קשה כיום לראותן. בין הכתובות היו שמולאו בצבע כדי להבליט את הכתובת על פני האבן, ובשאר הכתובות - עם חלוף השנים הצבע נעלם או הוסר והכתובות התמזגו עם גון האבן.
הכותל במסורת היהודית.
קדושת המקום.
במקרא ובמסורת היהודית לאורך הדורות, נחשב מקום בית המקדש למקום הקדוש והמרכזי ביותר. אחד הביטויים לכך הוא ההלכה שבשעה שמתפללים מכוונים את הלב לכיוון ירושלים והמקדש.
על הר הבית חלים דיני קדושה שונים. לפי דיני קדושה אלו נאסרו חלקים שונים ברחבי הר הבית לכניסה שלא בטהרה ושלא בקיום תנאים מיוחדים נוספים. גם לאחר חורבן הבית הקדושה עדיין קיימת באותם המקומות ומחמת שלא ניתן היום להיטהר מטומאת מת הרי שעל פי ההלכה היהודית הכניסה לחלקים מסוימים מהר הבית (אזור המקדש והעזרות) אסורה באיסור כרת. מאחר שתקופה ארוכה לא הורשו יהודים להיכנס אל ירושלים ואל הר הבית, לא נשארה מסורת ברורה היכן בדיוק המקומות המותרים בו. תפילה מול כתליו השונים של הר הבית הייתה המקום הקרוב ביותר שלא היה ספק לגביו. מאוחר יותר זכה כותלו המערבי של הר הבית למעמד מיוחד לעומת שאר הכתלים.
בדרך כלל מדרשי האגדה המזכירים את הכותל המערבי מתייחסים בלשונם לכותלו של בית המקדש (שנחרב לבסוף, לכל המאוחר במאה השביעית), ולא לקיר התמך המערבי של הר הבית כולו - הכותל המערבי של ימינו. כך למשל במאמר . מאז שלהי ימי הביניים ביטוי זה מאוזכר ומצוטט רבות בכתבי המחברים ועולי הרגל השונים בהקשר לכותל של ימינו. יש הטוענים שקישור זה הוא מאוחר ואינו כוונת המדרש. אך במדרש "איכה רבה", יש כרוניקה המתארת את חורבן כותלי חומות ההר, ואת הדרך בה נשתייר הכותל המערבי. שם גם מופיע הנימוק לכך שדווקא כותל זה נותר על מקומו. עם השנים, כאשר נתקבע הכותל המערבי כמקום תפילה מרכזי ובעל חשיבות רבה, התרחב השימוש בציטוט המדרשים השונים כדרך לתאר את מידת חשיבותו של הכותל של ימינו.
תקופת המשנה והתלמוד.
תפילות של יהודים ועלייתם לאתרים סביב קירות הר הבית מוזכרות בתלמוד כבר לגבי חכמים בדור שלאחר החורבן, אולם לאחר מרד בר כוכבא אסרו הרומאים על יהודים לבוא לירושלים. תפילות של יהודים מול קירות הר הבית מתועדות החל מהמאה הרביעית בסיפורי נוסעים ועולים לרגל. עדות ראשונה לכך נמצאת בדבריו של "הנוסע מבורדו" - עולה רגל נוצרי, שהגיע לירושלים בשנת 333:
התיאור מתייחס ככל הנראה לטקסי האבלות של תשעה באב. מקומה של "האבן הנקובה" אינו ברור, אך לצד ההנחה שהכוונה לאבן בכותל המערבי, שכן הוא מופיע בפירוש בתיאורים דומים נוספים, יש שמעריכים שהיא עמדה דווקא באזור הפינה הדרומית-מזרחית של הר הבית. באותה תקופה הוטלו מגבלות חמורות על כניסת יהודים לירושלים, כך שיהודים פקדו בעיקר את הר הזיתים, שממנו היה אפשר להשקיף על הר הבית. כיוון שכך, ייחסו יהודים חשיבות מיוחדת דווקא לכותל המזרחי של חומת הר הבית, כיוון שהוא הנשקף מהר הזיתים, וכיוון שממנו יצאו הכהן הגדול ועוזריו להכין אפר פרה אדומה בתקופת המקדש.
בימי הביניים.
עד למאה השביעית, עמדו בשממונן חורבותיו של בית המקדש. בשנת 614 גורשו הביזנטים על ידי הפרסים, שנעזרו ביהודים במלחמותיהם בארץ ישראל ובירושלים, ואלו העניקו ליהודים חופש פעולה מסוים שעורר תקוות משיחיות בקרב היהודים, שאף היו מעורבים בהרס הכנסיות שחוללו הפרסים. כעבור זמן לא רב חל מפנה בעמדת הפרסים, שנטו אחר כך להעדיף לטפח את קשריהם עם המוני הנוצרים בשטחים שכבשו. השינוי בעמדתם של הפרסים הביא לקיצו את הניסיון היהודי להפוך את ירושלים לעיר יהודית.
עם שובם של הביזנטים לשלוט בירושלים בשנת 628 נפרעו מן היהודים על תמיכתם, וחוללו הרס בהר הבית. הכותל המערבי של הר הבית ניזוק פחות, שכן למרגלותיו שכנה שכונת מגורים, שהרס הכותל היה מחייב את פינוייה. הארכאולוג מאיר בן דב, שהיה מנהל החפירות הארכאולוגיות ליד הר הבית ופיקח על חפירות הכותל, סבור כי בתקופת הרס זו החלה בניית "כנסיית ניצחון" מתומנת על הר הבית, צורה אדריכלית מקובלת במבנים נוצריים דומים, ודומה לזו של הכנסייה בגריזים. אך זמן לא רב אחרי שובם של הביזנטים, בשנת 638, נכבשה ירושלים בידי המוסלמים. אלו שיפצו והגביהו את כתליו החרבים למחצה של הר הבית, הקימו מבני ציבור של הח'ליפות סמוך לכותל המערבי. הם בנו, אולי על בסיס יסוד הכנסייה הביזנטית, את מבנה כיפת הסלע.
בראשית התקופה הערבית הראשונה הגיעו לירושלים כשבעים משפחות יהודיות מטבריה, בהזמנת השלטון החדש אשר נזקק למלאכות שבהן עסקו. יהודים אלה קבעו את מקום מגוריהם בסמוך לכותל הדרומי של הר הבית. נאסר עליהם להיכנס להר הבית, שאותו הפכו המוסלמים לאתר הקדוש להם.
על תפילות היהודים בסמוך לכתלים הדרומי והמזרחי של הר הבית בתקופה הערבית הראשונה, כותב מאיר בן דב:
הרמב"ם אשר שהה בארץ ישראל בשנים 1165–1166, שביקר בירושלים למשך שלושה ימים, נכנס כנראה להר הבית עצמו להתפלל אך אינו מזכיר ביקור באחד מכתליו של ההר.
בנימין מטודלה, שביקר בירושלים בשנת 1170 בערך, מזכיר מקום מול כיפת הסלע: "כותל מערבי, אחד מהכתלים שהיו במקדש בקודש הקודשים, וקוראים אותו שער הרחמים, ולשם באים היהודים להתפלל בפני הכותל בעזרה". הוא מספר שהיהודים היו נוהגים ל"כתוב את שמם כל אחד ואחד על הכותל". תיאור דומה מופיע בספרו של רבי יצחק חילו, שבילי ירושלים, שיצא לאור ב-1333, וגם בתיאור זה נזכר "הכותל המערבי" עם הביטוי "שער הרחמים".
לדעת בן-דב בעקבות התפתחות הקהילה היהודית ברובע היהודי בראשות הרמב"ן שהחלה בשלהי המאה ה-13, ניתן לשער שהתפילה בכותל המערבי של הר הבית נקבעה במאה ה-14.
בראשית העת החדשה.
התיאור הראשון שאפשר לקשרו בוודאות למקום המוכר בימינו בשם "הכותל המערבי" נכתב בשנת 1488 בידי רבי עובדיה מברטנורא, בעקבות ביקורו בירושלים.
זמן קצר לאחר כיבוש ירושלים בידי העות'מאנים בשנת 1517, החל השלטון העות'מאני לשקם את העיר ואת המבנים שבה, ואף עודד יהודים ממגורשי ספרד להתיישב ברחבי האימפריה העות'מאנית בכלל, ובארץ ישראל בפרט. לפיכך, יהודים רבים יותר יכלו לפקוד את המקום והכותל המערבי הוכר כאתר תפילה יהודי באופן רשמי על ידי השלטונות בפקודת הסולטאן סֻלמאן. התפילה נערכה בסמטה צרה ליד קטע קטן שאורכו היה עשרים מטרים, ובמרחק של כ-110 מטרים מצפון לפינה הדרומית-מערבית.
במהלך המאה ה-16 התרבו התיאורים של הכותל המערבי ברשימותיהם של נוסעים יהודים, רבניים וקראים, ונראה שבתקופה זו כבר הפך המקום לאתר תפילה יהודי מוכר וסמל קדוש ליהודי התפוצות. מתקופה זו ישנם מקורות בהם חכמי ישראל מייחסים למעמד התפילה הסמוך לכותלו המערבי של הר הבית, יחס נכבד בדומה לעמידה בפני כותלו המערבי של בית המקדש.
במאה ה-19 נאלצו היהודים לשלם לשלטונות העות'מאנים עבור הזכות להתפלל ולקונן ליד הכותל. הקונסול האמריקאי אלברט רודס מסר כי מדובר בתשלום שנתי בסך 1,500 דולר. משה מונטיפיורי קנה את הזכות לתמיד.
עוד במאה ה-19 ידוע על מנהג התחיבה של פתקים ברווחים שבין אבני הכותל.
הכותל במסורת המוסלמית.
הערבים כינו את הכותל אַלְגִ'דָאר אֶלְעַ'רְבִּי אך גם בשם "כותל הדמעות" או "כותל הבכי" (حائط المبكى, חאאֶ'ט אלמַבְּכּא), על שם תפילותיהם ובכיים של היהודים שבאו להתפלל שם, וכינוי זה התקבל מאוחר יותר גם לתיאור הכותל בשפה האנגלית (The Wailing Wall) ו"כותל הקינות" (Le Mur des Lamentations) בשפה הצרפתית.
באנציקלופדיה של האסלאם שיצאה בראשית המאה ה-20, בספרו של ההיסטוריון עראף אל-עראף, "ההיסטוריה המפורטת של ירושלים" וכן בספרי תיירות של הוואקף עד 1990 אין אזכור לכותל המערבי כקשור לאסלאם.
על פי ד"ר שמואל ברקוביץ', עד המאה ה-19 המסורת המוסלמית זיהתה את הכותל הדרומי או המזרחי כמקום אליו קשר הנביא מוחמד את הבהמה הפלאית שלו, "אל-בוראק", לאחר מסע הטיסה הלילי שלו ממכה לירושלים. כאשר התפתח המאבק סביב הכותל המערבי במאה ה-19, העתיקו המוסלמים, ממניעים פוליטיים, את מסורת זיהוי נקודת הקשירה של "אל בוראק" אל הכותל המערבי.
הכותל בעת החדשה.
בתקופת השלטון הבריטי.
לאחר כיבוש ירושלים בידי הבריטים בשנת 1917, ועם סיום מלחמת העולם הראשונה והתקופה העות'מאנית בארץ ישראל בשנת 1918, התגברה נוכחותם של יהודים תושבי הארץ ומבקרים מהתפוצות בכותל המערבי.