Marschen, som kan ta uppemot ett halvår och vars slutmål inte är uttalat, är en av många liknande protester som planeras av tibetanska exilgrupper inför OS.
På måndagen var det exakt 49 år sedan Dalai lama, Tibets andlige ledare, påbörjade flykten från Tibet efter ett misslyckat uppror mot det kinesiska kommunistpartiet, som styrt Tibet sedan 1951.
Dalai lama, som i ett uttalande nyligen ställde sig bakom att Peking ska arrangera OS och som av kritiker kallats för "mjuk", var nu arg i sin kritik av Kina.
- Förtrycket fortsätter och förstärks med många otänkbara och grova brott mot mänskliga rättigheter och med förnekelse av religionsfrihet och politisering av religiösa frågor, sa han inför hundratals supportrar i den indiska staden Dharmsala, enligt nyhetsbyrån AP.
Tibetaner har tvingats leva i skräck för kineserna i nästan sex årtionden, konstaterade Dalai lama, och talade om ökat och mer våldsamt förtryck som pågått under de senaste fem åren.
- Allt detta beror på den kinesiska regeringens brist på respekt för det tibetanska folket, sa den 72-årige mannen som fick Nobels fredspris 1989.
Vid sidan av att skicka sina olympiska trupper borde det internationella samfundet påminna den kinesiska regeringen om dessa frågor, anser Dalai lama, enligt AP.
- Kina borde även erbjuda tibetanerna dessa friheter för att visa att landet är en bra värd, fortsatte han.
Sedan 2002 har förhandlingar pågått mellan Peking och Dalai lama och hans ombud, som knappt lett någonstans. Men Dalai lama säger sig inte ha gett upp kampen för självstyre och fick på måndagen medhåll av Samdhong Rinpoche, Tibets premiärminister i exil.
- Vi har ingen dold agenda eller några andra frågor än det grundläggande kravet att Peking borde genomdriva det nationella regionala självstyre som redan står inskrivet i grundlagen, hävdade Rinpoche, enligt internationella nyhetsbyråer.
Samtidigt som marschen startade från Dharmsala i Indien, som är ett centrum för exiltibetaner, hölls demonstrationer av tibetaner i New Delhi och Nepals huvudstad Katmandu, där ett tiotal aktivister greps.
Sammanlagt är det fem kampanjgrupper för Tibet som organiserar marschen. Exakt vilken väg de gående demonstranterna tar är inte känt eftersom indiska myndigheter har förbjudit exiltibetaner att använda Indien som bas för demonstrationer mot Kina. På kvällen kom beskedet från indiska myndigheter att demonstranterna kommer att stoppas av polis om de försöker lämna distriktet där Dharamsala ligger.
Det är även okänt var någonstans längs den nästan 400 mil långa gränsen den protesterande gruppen planerar att gå in i Tibet.
Den yngsta medlemmen i marschen medförde enligt uppgift en teddybjörn och hembakta kakor. Tio i gruppen är kvinnor, del flesta är munkar.
Varje år beräknas cirka 3.000 tibetaner bege sig i den andra riktningen mellan Tibet och Nepal och vidare till Indien. De flesta saknar pass och ser ingen annan chans än att lämna Tibet över de fyra bergspass som vanligen används.
Många föräldrar på den tibetanska landsbygden tror att deras barn kan hitta ett jobb och klara sig bättre ekonomiskt i Indien än i Tibet. Men några omkommer också varje år under den hårda och långa fotvandringen över snöiga bergspass.