Han hade varit arbetslös sedan han skildes åt med Robins i november.
Crawley, som förvisades från League One tidigare denna månad, hade varit utan en manager sedan John Gregory lämnade West Sussex klubben den 9 maj.
"Mitt jobb är att sätta ihop en tävlingsgrupp som kommer att utmana i rätt ände av bordet," 45-årige Yates berättade Crawley webbplats.
Han tillbringade nästan fem år som chef för Cheltenham och guidade dem till League Two play-offs under 2012 och 2013.
Efter successiva topp-sju avslutar och misslyckade play-off kampanjer, Cheltenham slutade 17: e i League Two under 2013-14.
Och ex-Kidderminster boss Yates sparkades sedan sent förra året, efter en körning av fyra på varandra följande liga nederlag som lämnade dem 18: e.
Han var den tredje längsta avdelningschefen i Englands fyra största divisioner när han avgick från Whaddon Road.
"Jag har varit ute ur spelet i några månader och när denna möjlighet kom upp det verkligen upphetsade mig," sade han.
"Det finns en stor utmaning framför mig men en som jag verkligen ser fram emot."
Gregory, 60, separerade sällskap med Crawley tidigare denna månad, efter att ha tillbringat de senaste sex månaderna återhämta sig från hjärtkirurgi.
Dekanus Saunders fick interimistiskt ansvar för de röda i december, men kunde inte rädda klubben från släppet till League Two.
Den 50-årige f.d. Liverpool och Aston Villa-strejkaren utsågs till Chesterfield-chef förra veckan.
Crawleys verkställande direktör Michael Dunford sa att Yates stod ut bland "en del mycket starka kandidater".
Han tillade: "Han har en mycket djup kunskap om den nivå vi befinner oss vid nästa säsong och är en förstklassig tränare.
"Styrelsen talade till flera personer i spelet som har arbetat med Mark och de var alla mycket positiva om hans meriter, hans kunskap och hans entusiasm."
Crawley Town har utsett den tidigare Cheltenham chefen Mark Yates till sin nya chef på ett tvåårigt avtal.