در حالی که ارتش اصلی صلیبی در سال 1097 در سراسر آسیای صغیر لشکرکشی می کرد، بالدوین و نورمن تانکرد لشکرکشی جداگانه ای را علیه
کیلیکیه راه اندازی کردند.تانکرد در سپتامبر سعی کرد تارسوس را تصرف کند، اما بالدوین او را مجبور به ترک آن کرد که باعث درگیری پایدار بین آنها شد.بالدوین با کمک
ارامنه محلی قلعه های مهمی را در سرزمین های غرب فرات تصرف کرد.لرد ارمنی ادسا، توروس، فرستادگانی - اسقف ارمنی ادسا و دوازده شهروند برجسته - را در اوایل سال 1098 به بالدوین فرستاد تا از او در برابر فرمانروایان
سلجوقی نزدیک کمک بخواهند.ادسا به عنوان اولین شهری که به مسیحیت گروید، نقش مهمی در تاریخ مسیحیت ایفا کرد.بالدوین در اوایل فوریه عازم ادسا شد، اما نیروهایی که توسط بالدوک، امیر ساموساتا یا باگرات فرستاده شدند، مانع از عبور او از فرات شدند.تلاش دوم او با موفقیت همراه بود و در 20 فوریه به ادسا رسید.بالدوین نمی خواست به عنوان یک مزدور به توروس خدمت کند.اهالی ارمنی از اینکه او قصد ترک شهر را دارد می ترسیدند، بنابراین توروس را متقاعد کردند که او را به فرزندی قبول کند.بالدوین که توسط نیروهای ادسا تقویت شده بود به قلمرو بالدوک حمله کرد و پادگانی را در قلعه کوچکی در نزدیکی ساموساتا قرار داد.بر خلاف اکثریت ارمنی ها، توروس به کلیسای ارتدکس پایبند بود و همین امر او را در میان رعایای مونوفیزیت خود نامحبوب کرد.اندکی پس از بازگشت بالدوین از مبارزات انتخاباتی، اشراف محلی شروع به توطئه علیه توروس کردند، احتمالاً با رضایت بالدوین (همانطور که توسط وقایع نگار معاصر متی ادسا بیان شده است).شورش در شهر رخ داد و توروس مجبور شد به قلعه پناه ببرد.بالدوین متعهد شد که پدر خواندهاش را نجات دهد، اما وقتی شورشها در 9 مارس وارد قلعه شدند و توروس و همسرش را به قتل رساندند، او هیچ کمکی به آنها نکرد.در روز بعد، پس از اینکه مردم شهر بالدوین را به عنوان حاکم (یا دوکس) خود تصدیق کردند، او عنوان کنت ادسا را بر عهده گرفت و بدین ترتیب اولین
ایالت صلیبی را تأسیس کرد.بالدوین بیوه برای تقویت حکومت خود با دختر حاکم ارمنی (که اکنون به نام آردا شناخته می شود) ازدواج کرد.او در طول محاصره انطاکیه، غذای اصلی ارتش صلیبی را تامین کرد.او به مدت سه هفته از ادسا در برابر کربوغا، والی موصل دفاع کرد و از رسیدن او به انطاکیه قبل از تصرف صلیبیون جلوگیری کرد.