Amasya'da ulusal ihtilal kararları alınırken, Erzurum'da "Vilayet-i Şarkiye Müdafaa-i Hukuk Cemiyeti" nin düzenlediği bir kongre toplanması için çalışılıyordu. Doğu Anadolu'nun Ermenilere verileceği haberinin duyulması Damat Ferit Paşa'nın, doğu illerinin Ermenistan'a bırakılması konusunda yumuşak ve teslimiyetçi politikası anlaşılınca, bu illerinin bütün Müslüman halkının, haklarını savunmak için İstanbul'da kurulmuştu. Savaş sonrası terhis dan Cevat Dursunoğlu, memleketi Erzurum'da öğretmenlik yapmak için Maarif Vekaleti'ne başvurduğunda "Erzurum'un mukadderatı, yani hudutlarımızın içinde kalıp kalmayacağıhenüz belli olmadığından, orada bir Dar'ül-muallimin açmaya lüzum kalmamıştır" yanıtını almıştı. Dernek merkezinden, Erzurum'da bir şube açma yetkisini alan Cevat Dursunoğlu Erzurum'a gelerek burada bir şube açtı. 10 Mart 1919'da kurulan Erzurum Müdafaa-i Hukuk Şubesi hızla örgütlenmeye, çevre illerle, özellikle Trabzon'la ilişki kurarak, Doğu Anadolu'nun Ermenistan'a verilmesini engellemek için çalışmaya başladı.

Tarih boyunca Anadolu'nun kapısı olan Erzurum, son yüz yılda Türk-Rus Savaşları'nın en yoğun geçtiği bir şehrimizdi. Erzurum'a yeni gelen Cevat Dursunoğlu, şehri ve çevresini şöyle anlatıyor:

"Birinci Dünya Savaşı süresince Ruslarla yapılan savaşlar dolayısıyla, köylerin çoğu boştu. İçerilere göç etmiş bulunanların pek azı geri dönmüştü. Amansız kış iklimi yoksul halkı çok perişan etmişti. Dört yıl çetin kış savaşları yüzünden insan eti yemeye alışmış kurt sürüleri tehlike yaratıyordu. Erzurum şehri bir enkaz yığını olmuştu. Savaştan önce seksen bin nüfusu rahatça besleyen, çarşı ve pazarları kalabalıktan geçilmeyen bu sınır kentinden kocaman bir köy harabesi ortada kalmıştı. Savaş yıllarında onbinlerce insan tifüsten ve çeşitli bulaşıcı hastalıklardan ölmüş, istila öncesinde eli, ayağı tutanlar muhacir olmuş, on bin kişiyi de Ermeniler çekilirken öldürmüşlerdi. Şehirde kılıç artığı olarak üç dört bin kişi kalmıştı. Bu kadar da köylerden buraya göç etmişlerdi... Õlümden kurtulanlar ve geri dönenler, yangınlardan ve patlayan cephaneliklerin depremlerinden arta kalan eski refahlı evlerinin harabelerinde birer ikişer oda tamir ederek içine sığınmışlardı.."

Şehirde hiç Ermeni bulunmamasına rağmen, Erzurum'un Ermenistan'a verileceği haberi Erzurumluları galeyana getirirken, İzmir'in Yunanlılar tarafından işgali bütün yurtta olduğu gibi Erzurum'da da bomba gibi patladı. Müdafaa-i Hukuk üyeleri hemen bir miting heyeti kurarak Erzurum ve çevresindeki yerlerde İzmir'in işgalini protesto ettiler. Doğu Anadolu halkı galeyana gelmiş, hak arayan sesini bütün dünyaya duyurmaya çalışıyordu. İzmir'in başına gelenlerin Erzurum'un başına da gelebileceği belirtilerek önlem alınması isteniyordu.

Çevre illerle de ilişki kurarak çalışma alanını genişleten Erzurum Müdafaa-i Hukuk Cemiyeti, ne kadar güçlenirse güçlensin, ordunun desteği olmadan tam bir başarı sağlanamayacağını biliyordu. Diğer yandan Trabzon şehrinin Rumlara verileceği endişesi ile Trabzon'da kurulmuş bulunan Trabzon Müdafaa-i Hukuk Cemiyeti'nin teşvikiyle Erzurum Müdafaa-i Hukuku, Erzurum'da bir vilayet kongresi toplamaya karar verdi. "Vilayet-i Şarkiye Kongresi" sözü ilk kez, bu kongre için yapılan ön toplantılarda kullanıldı. Yine bu toplantılarda, bütün doğu illerini bir fikir etrafında toplamak ve mutlaka ordu ile birleştirmek kararı alındı.Erzurum Müdafaa-i Hukuku'nun bu çalışmaları 15. Kolordu Komutanı Kazım Karabekir Paşa'nın 3 Mayıs 1919'da Erzurum'a gelmesiyle büyük bir destek ve güç kazandı. Dernek bir yandan ordu ile yakın ilişki içindeyken diğer yandan Albayrak Gazetesi ile de propaganda yapıyordu.

Vilayet Kongresi, sancak ve kazalardan gelen delegelerin katılmasıyla 17 Haziran 1919'da Başkan Raif Efendi'nin konuşmasıyla açıldı. Alınan kararları şu iki prensipte toplamak mümkündür:

1- Osmanlı camiasından, yani vatanından ayrılmamak için her türlü ihtimali göz önüne alarak, bu yolda hiçbir fedakarlıktan kaçınmamayı ve hiç göç etmemeyi "ilke" olarak kabul etmek.

2- Her ne suretle olursa olsun, memleket bir Ermeni saldırısına uğrarsa bunu şiddetle karşılamak ve ulusal varlığımızı son ferdin ölümüne kadar korumak Ayrıca Ermeni propagandasına karşı da on sekiz sayfalık bir broşür yayınlayarak, Kürt-Türk kardeşliğini, gelenek ortaklığını tarih ve bilim açısından ele alıp Ermeniler'in bölücü propagandasını çürütüyordu.

Erzurum'da bulunan İngiliz Yarbay Rawlinson, bu çalışmaları engellemek için elinden geleni yaparken, Mondros hükümlerine dayanarak, silah ve cephaneyi Trabzon yoluyla göndermek için çalışıyordu. Fakat Kazım Karabekir Paşa, kendisine bu olanağı vermiyordu.Yine bu tarihlerde A.B.D. adına "Ermenistan" sorununu araştırmak üzere General G. Harbord Heyeti Erzurum'a gelerek incelemelerine başlamıştı. Harbord'a, Müdafaa-i Hukuk'un yaptığı bir toplantıda Erzurum'un bir Türk ili olduğu anlatıldı. Belediye Başkanı Zakir Bey, Harbord'a, Gez Mahallesi ve Kavak Mezarlıkları'nı göstererek şu ilginç konuşmayı yaptı:

"Şu geniş taşlıkları görüyormusun? İşte bunlar Türk mezarlıklarıdır. Şehrin öbür yanlarında da daha bunun on misli mezarlıklarımız var. Simdi iyice bak. Şurada da da etrafı duvarla çevrilmiş küçük bir mezarlık var. O da Ermeni Mezarlığıdır. Şimdi Ermenilerin mi, Türklerin mi daha çok olduğunu anladın mı? Bunlar ölülerini yemediler ya." Bu somut kanıt Harbord'u, diğer açıklamalardan daha çok etkiledi.

Erzurum'da bu gelişmeler olurken, toplanacak Erzurum Kongresi'ne M. Kemal Paşa, Cemiyet ve Kazım Karabekir Paşa tarafından davet edildi. Diğer yandan İstanbul Hükümeti de M. Kemal Paşa'nın Havza ve Amasya'daki çalışmalarını öğrenmiş ve kendisini İstanbul'a çağırıyordu. Amasya Genelgesi'nde, ulusal birliğin sağlanması için toplanacak kongrenin yeri Sivas olarak belirlenmişti. Fakat Erzurum'un davetini kabul eden M. Kemal Paşa, Samsun'dan başlayan Amasya, Erzurum, Sivas üzerinden geçen ve Ankara'da B.M.M.'nin açılmasıyla noktalanan "Ulusal İradeyi Egemen Kılmak" için tarihi yolculuğuna Erzurum'u da katıyordu.

M. Kemal Paşa Erzurum'a gitmek üzere 25 Haziran'da Amasya'dan ayrıldı. Önce Tokat'a geldi. Bu sırada İstanbul Hükümeti, Elaziz (Elazığ) Valiliği'ne atanan Ali Galip aracılığı ile yeni bir engellemeye başvurdu. Kemal Bey Anadolu'ya yolladığı yeni emirle, M. Kemal Paşa'nın tutuklanıp İstanbul'a gönderilmesini istedi. Ali Galip de Sivas Valisi Reşit Paşa'ya baskı yaparak M. Kemal Paşa'yı tutuklamasını istedi. Tokat'tan ayrılmadan önce, kendisinin ayrılışından altı saat sonra çekilmek ve Sivas'a gittiğini bildiren bir telgraf metni bırakan M. Kemal Paşa, Sivas'a vardığında Vali'nin eline yeni geçmişti. Ali Galip'in girişimlerini bozan M. Kemal Paşa, Sivaslılar'ın coşkun sevgi gösterisiyle karşılandı. Burada fazla oyalanmadan Erzurum'a hareket etti.

3 Temmuz 1919'da Erzurumlular'ın coşkun sevgi gösterileri arasında Erzurum'a vardı. O'nun gelişiyle Erzurum büyük bir olaya sahne oluyordu. İstanbul Hükümeti'nin baskıları da bu ara iyice arttı.

M. Kemal Paşa'nın gelmesinden bir iki gün sonra bir gece,15. Kolordu'nun Komutanı Kazım Karabekir Paşa, Rauf (Orbay), Erzurum Valisi Münir (Akkaya), İzmit Mutasarrıfı Süreyya (Yiğit), Ordu Müfettişiliği Kurmay Başkanı Kazım (Dirik), Binbaşı Hüsrev (Gerede), Dr. Binbaşı Refik (Saydam) ve Mazhar Müfit(Kansu) Beyler'in katıldığı bir toplantı düzenlendi. Bu toplantıda konuşan M. Kemal Paşa, ülkenin içinde bulunduğu tabloyu açık bir şekilde ortaya koydu:

1- Muhasım devletler Osmanlı vatan ve Devleti'ni mahv ve taksimine karar vermiş bulunuyorlar. Bu kararlarını uygulayabilmek için de her çeşit maddi ve manevi saldırıları yapmaktan geri kalmıyorlar. Hükümet muhasımların her çeşit saldırı ve emirlerine miskince boyun eğmekte, her çeşit zillete katılmaktadır. Padişah ise ünvanı saklı ve daimi kalmak şartıyla her şeye razı bulunuyor.

2- Ulus karanlık içinde muzdarip ve perişan bir haldedir, geleceğinin ne olacağını merak etmekte ve kurtuluş çaresi kabul ettiği her çeşit özel tedbire başvurmakta, memleketi kurtarmak ve savunmak ümidi ile çeşitli yerlerde, çeşitli isimler ile dernekler kurmaktadır.

3- Ordu, genel savaşın (Birinci Dünya Savaşı) binbir meşakkatı ile yorgundur. Yorgunluğuna ve hatta bitkinliğine rağmen vatanın parçalanmak istediğini görerek önleyici çareler aramakla cidden meşguldür.

4- Günün içinde üç fikir çarpışmaktadır:
a) Galip devletlerle savaş yapamayacağımıza göre uysal fedâkar ve uyuşkan hareket etmek.
b) Padişah re çevresinde toplanmak ve düvel-i muhasamanın Padişah ve Halife için egemenlik hakkı tanıyacağı bölgede Osmanlı Devleti'ni devama gayret etmek.
c) Osmanlı Devleti'nin paylaşılması kararlaştırıldığına göre ırk ve bölge özelliklerine önem vermek ve bu olanaktan yararlanarak yerel kurtuluş çareleri aramak. Vaziyet arz ye izah ettiğim bu safhalar içinde bulunurken ne yapmak lazımdır? Sorusunu izin verirseniz ben kendi düşüncelerime göre cevaplandırayım. Arkadaşlar, tek tedbir : Ulusal Egemenliğe dayanan kayıtsız şartsız bağımsız bir Türk Devleti kurmak ve bu hedefe mutlaka ulaşmaktır." Bu amaca ulaşmak için ileride çıkacak güçlükleri ve tehlikeleri bütün açıklığıyla ve büyük bir ileri görüşlülükle belirterek sözlerine devam eder:

"Hedefimiz bu olacaktır. Kolay degil. İdealimizi gerçekleştirmek yolunda şimdiden şahıs şahıs yükleneceğimiz görevler ağır, müşkül, hatta tehlikeli olacaktır. Ulusal Mücadele'de, topyekün mücadele esastır. Büyük direnmelerle hatta hıyanetlerle karşılaşacağımız bir gerçektir. Ulusal Mücadele'ye atılanların mahv ve yok olması için, Saray, Hükümet, yabancılar muhakkaki ilk andan itibaren harekete geçeceklerdir. Ayrıca yer yer memleket halkının da iğfal edilmesi, isyanlar,ihtilaller çıkartması ve bütün bu olumsuz hareketlerin Ulusal Müücadele aleyhine yöneltilmesi yüksek bir olasılıktır. Daha kimbilir, akla gelen ve gelmeyen ne entrikalar, ne fesatlar, ne tuzaklarla karşılaşacagız. Ulusal Mücedele'yi ulusun büyük çoğunluğuna dayanarak süratle hızlandırmak ve organize etmek zorundayız. Memlekette ve elimizde tek tepe ve tek kurşun kalıncaya kadar mücadele etmek azmimiz daima saklı kalacaktır ve kalmak zorundadır. Görüyorsunuz ki arkadaşlar, yürüyeceğimiz bu yol tehlikelerle, hatta ölmek ve öldürmek olasılıkları ile doludur. Sarp ve haşin bir yoldur. Bu tehlikelere göğüs germeye kendisinde güç, azim, olanak ve cesaret görmeyen arkadaşlarımız varsa, şimdiden aramızdan ayrılabilirler. Ancak bu saydığım tehlikeleri, olasılık ve yorgunlukları göze alabilenlerdir ki benimle işbirliğini kabul etmiş olurlar." Hiçbir arkadaşı ayrılmayacak sonuna kadar O'nunla birlikte yürüyecektir. O'nu lider seçerler ve emirlerine kayıtsız şartsız uyacaklarını bildirirler. Bu yolda Atatürk'ün koyduğu parola tektir. "YA ÖLÜM YA BAŞARI VE ZAFER."