Գարեգին Նժդեհը ծնվել է 1886 թվականի հունվարի 1-ին Ռուսական կայսրությունում՝ Երևանի նահանգի Նախիջևանի գավառի Կզնուտ (այժմ՝ Գյուզնութ) գյուղում։

Սկզբնական կրթությունը ստանալով տեղի ծխական հայկական դպրոցում, իսկ այն փակվելուց հետո Նախիջևան քաղաքի ռուսական դպրոցում՝ ուսումը շարունակում է Թիֆլիսի ռուսական գիմնազիայում, որտեղ սովորելու ընթացքում էլ, 17 տարեկան հասակից, միանում է հայ ազատագրական շարժմանը։ Այնուհետև մեկնել է Սանկտ Պետերբուրգ և երկու տարի տեղի համալսարանի իրավաբանական բաժնում սովորելով՝ թողնում ուսումը և ամբողջովին նվիրվում հայ հեղափոխության գործին՝ ընդդեմ ցարիզմի ու սուլթանականության։ 1906 թ.-ին անցնում է Բուլղարիա, որտեղ Ռոստոմի աջակցությամբ և մակեդոնական ազատագրական շարժման ղեկավարների միջնորդությամբ ընդունվում է Սոֆիայի սպայական դպրոցը և այն հաջողությամբ ավարտելով՝ 1907 թվականին վերադառնում է Հարավային Կովկաս։

1907 թվականին մտնում է ՀՅԴ շարքերը և մասնակցություն բերում պարսկական հեղափոխական շարժմանը։ Զենք և ռազմամթերք տեղափոխելու համար Նժդեհը 1909 թվականին վերադառնում է Կովկաս և ձերբակալվում ցարական իշխանությունների կողմից։ Բանտերում մնալով ավելի քան երեք տարի՝ մեկնում է Բուլղարիա։