הכיכר האדומה נוצרה בסוף המאה ה-15 כאשר בפקודת הצאר איוואן השלישי נהרסו מבני העץ סביב חומת הקרמלין בשל סכנת שרפה לארמון הצאר, ובמקומם הוקמה ליד החומה המזרחית כיכר למסחר קמעונאי. בין השנים 1508–1516 נחפרה תעלת מגן בעומק של 12 מטר בין חומת הקרמלין לבין הכיכר, ותעלה זו, שהייתה מוגנת בחומות, הייתה קיימת עד לאחר שנת 1812. בחלק הצפוני של הכיכר היו שערים לאזור המסחרי של העיר (קיטאי-גורוד) והשער היחיד שנותר מאלה הוא שער התחייה. בשנים 1555–1560 נבנתה כנסיית וסילי הקדוש בדרום הכיכר, במקום בו ניצבה קודם לכן כנסיית השילוש. בשנות ה-30 של המאה ה-16 נבנתה בכיכר בימה מיוחדת שזכתה לשם לובנויה מייסטו. הבימה שימשה להכרזת פקודות הצאר ולא הרחק ממנה היה מקום להוצאות הפומביות להורג. במהלך המאה ה-16 נבנו סביב הכיכר בנייני ממשלה ובנייני ציבור חשובים, ובבניין "בית המרקחת הראשי" של העיר החלה לפעול אוניברסיטת מוסקבה בשנת 1755. בשנת 1786 נבנה בחלק המזרחי של הכיכר בניין מסחרי חדש, ובשנת 1818 הוצבה אנדרטת מינין ופוז'ארסקי בחזיתו. בשנת 1930 הוזזה האנדרטה למקום אחר בכיכר שם היא ניצבת גם כיום. במהלך המאה ה-19 השתנה מראה הכיכר באופן מהותי. בין השנים 1875–1881 נבנה בצידה הצפוני של הכיכר המוזיאון להיסטוריה, ובחלקה המזרחי הוקם בניין מסחרי בשנים 1889–1893. הבניינים נבנו בסגנון מעין רוסי ישן, כך שידמו לחומותיו ולמגדליו של הקרמלין.

בתקופה הסובייטית הוקמו המאוזוליאום של לנין (1929-1930) ובמות לישיבת אחמ"ים (1930-1931). באותה תקופה נשתלו עצי אשוח לאורך חומת הקרמלין. בתקופה זו גדלה חשיבותה של הכיכר והיא הייתה לכיכר המרכזית במדינה, אשר שימשה לעריכת מצעדים צבאיים ולהפגנת העוצמה הסובייטית. הכנסיות שהפריעו למצעדים (קתדרלת קאזאן והקפלה האיוורית ליד שער התחייה) נהרסו, ומקובל שגם כנסיית וסילי הקדוש נועדה להריסה. על המצעדים החשובים שנערכו בכיכר נימנים מצעד אחד במאי לפני הפלישה הגרמנית, המצעד שנערך בנובמבר 1941 כאשר הצבא הנאצי הגיע לקרבת מוסקבה ומצעד הניצחון ב-1945.

ב-28 במאי 1987 נחת מתיאס רוסט, טייס חובב ממערב גרמניה עם מטוס קל בלב הכיכר האדומה (אזור אסור לטיסה). הנחיתה עברה בשלום לאחר מעבר כל מערכות ההגנה האווירית ההדוקה של בירת ברית המועצות, העמידה במבוכה את הצמרת הסובייטית. עקב המקרה פיטר הנשיא מיכאיל גורבצ'וב את שר ההגנה הרוסי סרגיי סוקולוב ואת ראש מערך ההגנה האווירית אלכסנדר קולדונוב, שניהם גיבורי מלחמת העולם השנייה ונציגי המשטר הישן.

בתחילת המאה ה-21 משמשת הכיכר גם לקונצרטים שונים, והופיעו בה פול מקרטני, פינק פלויד, רד הוט צ'ילי פפרז ואומנים ידועים נוספים. מסורת המצעדים הצבאיים בכיכר חודשה כבר בשנות ה-90 של המאה ה-20, והיא נערכת פעם בשנה בחגיגות יום הניצחון, למרות הקושי בהעברת כלי רכב כבדים לאחר הקמת כנסיות שנהרסו בשנות ה-30 של המאה ה-20.

מאז 2009 נערך בכיכר, מדי שנה, גם פסטיבל בינלאומי למוזיקה ותזמורות צבאיות הזוכה להתעניינות ציבורית רבה ברוסיה ובעולם.