Han talade till tusentals människor i huvudstaden, Kigali, när Rwanda började en vecka av officiell sorg för att markera 20-årsdagen av folkmordet.
Många blev överväldigade av känslor under ceremonin, med vissa lidanden.
Minst 800.000 människor - mestadels etniska tutsier och moderata hutuser - dog i händerna på hutuextremister.
Morden upphörde i juli 1994 när den rwandiska patriotiska fronten (RPF), en tutsiledd rebellrörelse, marscherade in i Kigali och tog kontroll över landet.
Rwandas president Paul Kagame och herr Ban tände en fackla som kommer att brinna i 100 dagar - den tid folkmordet varade.
En diplomatisk rad har fått Rwanda att hindra Frankrikes ambassadör, Michel Flesch, från att närvara vid evenemanget, rapporterar nyhetsbyrån AFP.
Av Charlotte AttwoodBBC Afrika, Kigali
Det började med bara ett enda, och sedan ekade mängder av rysande skrik runt stadion.
Det kanske är 20 år kvar, men för många här är såren fortfarande för färska för att bära. Paramedikerna gick upp och ner på terrasserna, tröstade och tog bort dem som inte kunde klara av minnena. Jag såg en man bli avrättad under dramatiseringen av Rwandas senaste historia.
Själva pjäsen var en mycket tydlig skildring av regeringens tolkning av vad som orsakade den tragiska händelsen i landets historia.
Halvvägs igenom körde en jeep med "koloniäristerna" som marscherade upp på scenen. De bytte ut sina koloniala halmhattar mot FN:s blå hjälmar och övergav sedan folket och lämnade ett blodbad efter sig. Soldater som representerar den styrande RPF - truppen för att rädda en förkrossad befolkning.
Sörjningsveckan inleddes med en kransläggningsceremoni vid det nationella folkmordets minnesmärke, följt av en eldslåga på Amahoro Stadium i Kigali, där FN:s fredsbevarare skyddade tusentals människor under folkmordet.
Torken har transporterats över landet under de senaste tre månaderna, besökt 30 distrikt och gått från by till by.
Tusentals människor packade stadion och köade i timmar genom dimman, rapporterar BBC: s Charlotte Attwood från scenen.
Många av dem reagerade med okontrollerbara känslor på berättelserna, talen och föreställningarna som påminde om folkmordet, säger vår korrespondent.
En del av dem måste ledas ut ur stadion medan andra fick anfall, tillägger hon.
Traditionella sorgesånger sändes över ljudsystemen.
Det förekom också en dramatisering av Rwandas senaste historia, som vår korrespondent säger var en tydlig skildring av regeringens tolkning av händelserna.
I pjäsen kommer en jeep med "kolonialister" som byter sina halmhattar mot FN:s blå hjälmar. De överger sedan folket, som räddas av den styrande RPF.
FN:s personal i Rwanda under folkmordet visade "trovärdigt mod", berättade Ban för folkmassan, enligt AP.
"Men vi kunde ha gjort mycket mer. Vi borde ha gjort mycket mer, sa han.
"I Rwanda drogs trupper tillbaka när de behövdes mest", tillade han.
"Ett år senare i Srebrenica, områden som proklamerats'säker' av FN var fyllda med fara, och oskyldiga övergavs till slakt. Skammen klamrar sig fortfarande fast, en generation efter händelserna", sade Ban.
Hur folkmordet gick till
Minneshögtid i bilder
Dina frågor besvarades
Kagame sade att Rwanda var "helt knäckt" efter folkmordet, men att det hade lyckats förena sig.
"Det [ folkmordet] skulle helt enkelt aldrig ha hänt", tillade han.
Andra internationella ledare närvarande är Ugandas president Yoweri Museveni, f.d. Sydafrikas president Thabo Mbeki och f.d. brittiske premiärminister Tony Blair, som nu är rådgivare till Rwandas regering.
På söndagen deltog hundratals människor i en mässa i den katolska kyrkan Sainte-Famille i Kigali för att minnas dem som dog i själva kyrkan och på andra håll.
En talesman för Rwandas regering sade att Frankrike inte skulle vara representerat vid händelserna för att markera folkmordet.
Flesch berättade för AFP att han hade fått ett telefonsamtal från Rwandas utrikesministerium för att "underrätta mig om att jag inte längre är ackrediterad för ceremonierna".
Tidigare sade det franska utrikesdepartementet att Flesch skulle företräda Frankrike vid händelserna efter det att justitieminister Christiane Taubira ställde in planerna på att närvara efter en anklagelse från Kagame om att Frankrike hade deltagit i massmorden.
Frankrike var nära allierad med Habyarimanas regering.
I en intervju med den franska veckotidningen Jeune Afrique fördömde Kagame Belgiens och Frankrikes "direkta roll i den politiska förberedelsen för folkmordet".
Han sade också att franska trupper hade tagit en "aktiv" del i morden.
Frankrike har avvisat denna anklagelse, och Edouard Balladur, som var fransk premiärminister 1994, sade till Europa 1-radion: " Frankrike är på intet sätt delaktigt i folkmordet.
"Tvärtom, det av alla länder i världen var det enda som tog initiativ till att organisera en humanitär operation för att förhindra omfattande massakrer."
Frankrike skickade trupper som satte upp "säkra zoner" i Rwanda. Det står att de räddade tusentals liv, men Rwandas regering har länge sagt att de inte gjorde tillräckligt för att stoppa dödandet - och nu säger de att de arbetade med hutumiliserna som utförde slakten.
FN skäms fortfarande över sitt misslyckande med att förhindra folkmordet i Rwanda 1994, sade FN:s chefs Ban Ki-moon.