While the main crusader army was marching across Asia Minor in 1097, Baldwin and the Norman Tancred launched a separate expedition against Cilicia. Tancred tried to capture Tarsus in September, but Baldwin forced him to leave it, which gave rise to an enduring conflict between them. Baldwin seized important fortresses in the lands to the west of the Euphrates with the assistance of local Armenians.

The Armenian lord of Edessa, Thoros, sent envoys—the Armenian bishop of Edessa and twelve leading citizens—to Baldwin in early 1098, seeking his assistance against the nearby Seljuqs rulers. Being the first town to convert to Christianity, Edessa had played an important role in Christian history. Baldwin left for Edessa in early February, but troops sent by Balduk, the emir of Samosata, or Bagrat prevented him from crossing the Euphrates. His second attempt was successful and he reached Edessa on 20 February. Baldwin did not want to serve Thoros as a mercenary. The Armenian townspeople feared that he was planning to leave the town, so they persuaded Thoros to adopt him. Strengthened by troops from Edessa, Baldwin raided Balduk's territory and placed a garrison in a small fortress near Samosata.

Unlike the majority of the Armenians, Thoros adhered to the Orthodox Church, which made him unpopular among his Monophysite subjects. Shortly after Baldwin's return from campaign, the local nobles started plotting against Thoros, possibly with Baldwin's consent (as is stated by contemporary chronicler Matthew of Edessa). A riot broke out in the town, forcing Thoros to take refuge in the citadel. Baldwin pledged to save his adoptive father, but when the rioters broke into the citadel on 9 March and murdered both Thoros and his wife, he did nothing to help them. On the following day, after the townspeople acknowledged Baldwin as their ruler (or doux), he assumed the title of Count of Edessa, and so established the first Crusader state.

To strengthen his rule, the widowed Baldwin married an Armenian ruler's daughter (who is now known as Arda). He supplied the main crusader army with food during the siege of Antioch. He defended Edessa against Kerbogha, the governor of Mosul, for three weeks, preventing him from reaching Antioch before the crusaders captured it.