Baldwin was a younger son of Hugh I, Count of Rethel and Melisende of Monthléry. He was closely related to the lords of Courtenay and Le Puiset, and other noble families in the Ile-de-France. He was also a kinsman of the brothers Eustace III of Boulogne, Godfrey of Bouillon, and Baldwin of Boulogne, but their exact relationship is unknown. Historian Alan V. Murray says that the primary sources suggest that their connection "was not particularly close", and that Baldwin was most probably related to their mother, Ida of Lorraine. Thomas Asbridge says that Baldwin was the Boulogne brothers' second cousin.
He was the lord of Bourcq when he joined the army of Godfrey of Boulogne at the beginning of the First Crusade. The army departed for the Holy Land on 15 August 1096, and reached Constantinople on 23 December. The Byzantine emperor, Alexios I Komnenos, urged the crusader leaders to take an oath of fealty to him. Godfrey of Bouillon appointed Baldwin, Conon of Montaigu and Geoffrey of Esch to represent him at a meeting with Alexios in January 1097. After Godfrey and his principal commanders swore fealty to the Emperor, the crusader army was transferred to Asia Minor in February.
Baldwin of Boulogne and the Norman Tancred broke away from the main army to invade Cilicia around 15 September 1097. Baldwin accompanied them in Boulogne's contingent. He also participated in Boulogne's military campaigns against the Seljuq rulers of the fortresses on the plains near the River Euphrates. After seizing Ravendel, Turbessel and Edessa, Boulogne established the first crusader state, the County of Edessa, in early 1098.
Baldwin rejoined the main crusader army, which was marching towards Jerusalem, near Tyre in late May 1099. He and Tancred seized Bethlehem without a fight, because the town was inhabited by local Christians. The crusaders laid siege to Jerusalem, and shortly afterwards Baldwin and Tancred captured an old Muslim nobleman. After he refused to convert to Christianity, Baldwin's soldiers beheaded him at the Tower of David to frighten the defenders of Jerusalem. Jerusalem fell to the crusaders on 15 July. Baldwin left Jerusalem in the retinue of Robert II, Count of Flanders, in late August. Robert returned to Europe, but Baldwin remained in Syria. Geoffrey of Bouillon died on 18 July 1100. Baldwin of Boulogne decided to hurry to Jerusalem to take possession of Geoffrey's inheritance.