Sidibé joined Stoke City on a two-year contract on a free transfer in June 2005. Tony Pulis, who brought Sidibé to Stoke, was sacked just four days later. He performed as a lone striker for the early stages of the 2005–06 season, keeping Bruce Dyer on the bench. Eventually, new Stoke manager Johan Boskamp signed Sambégou Bangoura to play alongside him in attack. He scored his first goal for City in a 3–1 win against Norwich City in August 2005. However, he did not score again for another 15 games. He went on to make 47 appearances during the 2005–06 season scoring seven goals. Sidibé was more prolific during the 2006–07 season scoring nine goals as Stoke narrowly missed out on a play-off place.