The Levush (669:1) explains this week's selected Haftorah’s connection to Parshas Lech Lecha in pasuk 41:2: “Who inspired [the one] from the East, who would proclaim His righteousness and at [every] footstep?" The verse concludes, "May his [Avraham's] sword make [victims] like dust, and his bow like straw."
The Gemara in Taanis (21a) interprets this verse as referring to Avraham Avinu, who journeyed from Aram, east of Israel, to spread his faith in Hashem—a central theme of our parashah
Another connection between the Haftarah and the parashah lies in the verse’s imagery of dust and straw. The Gemara in Sanhedrin (108b) recounts how Avraham overcame the four kings in our Parsha by miraculously turning sand and straw into swords and arrows. For these reasons, this Haftarah is read with Parshas Lech Lech.