Punase väljaku rajamise aega ei ole võimalik kindlaks teha. Kõige tõenäolisemalt oli praeguse väljaku kohal vaba plats juba Kremli rajamise ajal – seda kaitseotstarbelistest kaalutlustest lähtudes, et vaenlane ei saaks Kremlile salaja ligi hiilida.

Linna väravate ette tekkis turg ja esialgu seda platsi nimetatigi Turuks (Торг). 13. sajandi lõpus asutati "Imelise Issanda Ilmutuse klooster koos Ülipüha Jumalaema Kuulutuse külgaltariga Moskvas turu taga" ja on võimalik, et siin mõeldigi turu all praegust Punast väljakut. Kuid see sissekanne Issanda Ilmutuse kloostri majaraamatus on märgatavalt hilisem kloostri asutamisest.

Esimene väljaku mainimine leetopissis pärineb aastast 1434: Varvarskaja tänavale turu taha Borissi ja Glebi kiriku juurde maeti Maksim Õnnis.

Sageli arvatakse, et väljak tekkis 15. sajandi lõpupoole, "kui pärast Kremli müüride ehitust loodi sinna vaba plats". Kuid tuleb arvestada, et sel ajal ei ehitatud Kremli müüre esimest korda, vaid tegu oli ümberehitusega, mille käigus Kremli pindala suurenes, ja suurenes just nimelt varasema müüri ees olnud lageda platsi arvelt.

Mõned autorid seovad väljaku ilmumise veelgi hilisema sündmusega, nimelt 1493. aasta aprillis toimunud tulekahjuga. Nimelt pärast seda tulekahju "suurvürst Ivan Vassiljevitši käsuga lammutati kirikud ja talud Neglimnaja taga ning müürist kuni lähimate majadeni loeti välja sada ja kümme sülda (235 m)". Kuid koht "Neglimnaja taga" ei sobi Punase väljaku kohta ja pealegi oli turg seal juba hiljemalt 1434. aastast.

Kuni 17. sajandi alguseni nimetati seda väljakut Turuks, alates 16. sajandi lõpust kasutati ka nimetust Suur väljak, kuid kõige sagedamini nimetati seda Põlenguks (Пожар Požar). Seda nimetust on seotud 1571. aasta tulekahjuga, kuid esimest korda kohtab seda juba 1534. aastal seoses Kitai-gorodi (eesti keelde tõlgitud tihti ekslikult "Hiinalinnaks", tegelikult tuleneb vene sõnast "kitõ" - e.k 'vaiad', 'talad'; puidust talad toestasid algset kivimüüri Kitai-gorodi ümber.[1]) müüri ehitamisega. Muidugi ei toimunud põlengud üksnes turul ja üldse ei ole kohane püüda seda nime seostada mingi konkreetse põlenguga, sest põleng oli tollal üldnimetus kohaliku kremli juures oleva platsi kohta, kus tavaliselt oli turg, aga mitte tingimata. Näiteks 1627 käskisid kirikuvõimud pärast Segaduste aja lõppu kõigis Venemaa linnades, mis mõnda aega olid Rzeczpospolita kontrolli alla kuulunud, kõik leedukeelsed (s.t ladina tähtedega) raamatud kokku korjata "ja Põlengul ära põletada". Sellest saab järeldada, et igas tollases linnas pidi olema Põleng (ilmnes, et enamikus linnades polnud ühtki leedukeelset raamatut). Ka Moskvas eneses nimetati dokumentides 16. sajandil kahel korral põlenguks Lubjanka väljakut, viimati 1581.

Punaseks väljakuks nimetati seda väljakut esimest korda 23. aprillil 1661. Uus nimetus tuli käibele väga järsku. Kui varasemaid nimetusi kasutati sageli paralleelselt ja isegi samas tekstis mitut, siis ametlikes dokumentides ei nimetatud seda väljakut enam kusagil muudmoodi kui Punaseks väljakuks. Viimast korda nimetati seda Põlenguks 1662. aastal kohtudokumentides, mis uurisid rahvarahutusi. Niisugune nime kiire ja täielik vahetus annab alust arvata, et tsaar Aleksei Mihhailovitš pidi vastava käsu andma.

Venekeelne sõna красный tähendab tänapäeval üksnes 'punast', aga minevikus ka 'ilusat'. Ekslikult on arvatud, et Punane väljak sai nime selle ääres asuva Vassili Õndsa kiriku (Vassili Blažennõi kirik, Jumalaema Kaitsmise kirik, kuni 17. sajandini ka Püha Kolmainu kirik, vene keeles Храм Василия Блаженного) järgi, mida peeti ilusaks. Punane väljak oli minevikus tänapäevasest väiksem. Vaga Vassili Õnnis suri 1552. aastal ja maeti Kolmainu kiriku juurde, mille kohale 1555–1561 kerkis tema järgi nimetatav kirik. Seda kohta nimetati esialgu Troitse väljakuks (kolmainu kiriku järgi), 1667. aastast on säilinud ka nimetus Pokrovski väljak (Jumalaema Kaitsmise kiriku järgi). 1661. aastal mainitakse esimest korda Vassili Õndsa väljakut. Alles 19. sajandil sai Vassili Õndsa väljak selle väljaku peamiseks nimeks ja alles 1924. aastal ühendati Vassili Õndsa väljak Punase väljakuga.

Alates 1993. aastast on Punasel väljakul keelatud pildistamine fotoaparaatidega, samuti statiivilt. Keelu alla käivad kõik fotoaparaadid, mille korpuse kõrgus on üle 14 cm ja objektiivi läbimõõt üle 7 cm. Vastavaid lube annab välja Moskva Kremli komandantuur. Loataotlus tuleb tingimata isiklikult esitada, sest faksi ja e-posti teel taotlusi vastu ei võeta. Loataotluse menetlemine kestab mitu päeva.

2001 keelati Punasel väljakul jalgrattaga sõitmine.

Väljak kuulub koos Kremliga UNESCO maailmapärandi nimistusse.