Terwijl het belangrijkste kruisvaardersleger in 1097 door Klein-Azië marcheerde, lanceerden Baldwin en de Normandische Tancred een afzonderlijke expeditie tegen Cilicië . Tancred probeerde in september Tarsus gevangen te nemen, maar Baldwin dwong hem het land te verlaten, wat aanleiding gaf tot een langdurig conflict tussen hen. Baldwin veroverde met de hulp van lokale Armeniërs belangrijke forten in de landen ten westen van de Eufraat.
De Armeense heer van Edessa, Thoros, stuurde begin 1098 gezanten - de Armeense bisschop van Edessa en twaalf vooraanstaande burgers - naar Baldwin, om zijn hulp te zoeken tegen de nabijgelegen Seltsjoeken- heersers. Als eerste stad die zich tot het christendom bekeerde, had Edessa een belangrijke rol gespeeld in de christelijke geschiedenis. Baldwin vertrok begin februari naar Edessa, maar troepen van Balduk, de emir van Samosata, of Bagrat verhinderden hem de Eufraat over te steken. Zijn tweede poging was succesvol en hij bereikte Edessa op 20 februari. Baldwin wilde Thoros niet als huursoldaat dienen. De Armeense stadsmensen waren bang dat hij van plan was de stad te verlaten, dus haalden ze Thoros over om hem te adopteren. Gesterkt door troepen uit Edessa, viel Baldwin het grondgebied van Balduk binnen en plaatste een garnizoen in een klein fort nabij Samosata.
In tegenstelling tot de meerderheid van de Armeniërs hield Thoros zich aan de Orthodoxe Kerk, wat hem impopulair maakte onder zijn monofysitische onderdanen. Kort na de terugkeer van Baldwin van de campagne begonnen de plaatselijke edelen samenzwering tegen Thoros te smeden, mogelijk met toestemming van Baldwin (zoals vermeld door de hedendaagse kroniekschrijver Matthew van Edessa). Er brak een rel uit in de stad, waardoor Thoros gedwongen werd zijn toevlucht te zoeken in de citadel. Baldwin beloofde zijn adoptievader te redden, maar toen de relschoppers op 9 maart de citadel binnendrongen en zowel Thoros als zijn vrouw vermoordden, deed hij niets om hen te helpen. De volgende dag, nadat de stadsmensen Baldwin als hun heerser (of doux) hadden erkend, nam hij de titel van graaf van Edessa aan en vestigde zo de eerste kruisvaardersstaat .
Om zijn heerschappij te versterken trouwde de weduwe Baldwin met de dochter van een Armeense heerser (die nu bekend staat als Arda). Hij voorzag het belangrijkste kruisvaardersleger van voedsel tijdens het beleg van Antiochië. Hij verdedigde Edessa drie weken lang tegen Kerbogha, de gouverneur van Mosul, waardoor hij Antiochië niet kon bereiken voordat de kruisvaarders het veroverden.