There are a number of stories of early presence of muslims in India. Thus, a malabar king (Chakrawarti Farmas) is said to have seen the splitting of the moon (estimated 617 AD) and have met the prophet Muhammad himself, and of a muslim community in India since 642 AD. (Another malabar community consists of very early chrstians as well.) Historically, we know of muslims being influencial in the western edge of India starting around 730 AD (city of Al mansura founded; Sind under the Abbasids in 750 AD; multan independent muslim state in India in 850 AD). They plundered a lot of north India, and starting in the 11th century started ruling in North India. However, their influence in Bengal started only towards the end of the 12th century, and this defines the beginning of the Medieval period in the history of Bengal.
Up to history of Muslim period in Bengal