Les Européens ont probablement exploré la baie pour la première fois au XVI siècle. Son pourtour est alors habitée par deux groupes d'Amérindiens : les Narragansetts à l'ouest, et les Wampanoags à l'est et dont les territoires de vie allaient jusqu'à Cape Cod.
La plupart des historiens considèrent que le premier contact avec des Européens eut lieu en 1524 avec l'entrée dans la baie du navire La Dauphine, commandé par Giovanni da Verrazano, après avoir visité la baie de New York. Verrazano baptise la baie « Refugio » (le refuge). Par contre, le débat historiographique se poursuit sur le circuit exact de La Dauphine - la baie ayant plusieurs entrées - et quelle tribu, il a pu rencontrer en premier.
En 1614, la baie est explorée et cartographiée par le Néerlandais Adriaen Block ; une île a été baptisée à son nom, île Block.
La première installation européenne est daté des années 1630. Roger Williams était un membre insatisfait de la colonie de Plymouth et s'installa dans la baie en 1635. Il instaura des contacts avec les Narrangansetts et établit un comptoir commercial sur le côté ouest de la baie. Environ une vingtaine de kilomètres au sud-ouest, les Néerlandais venaient d'installer leur comptoir sous l'autorité de la colonie de Nouvelle-Amsterdam dans la baie de New York.
En 1643, Williams voyagea en Angleterre et reçut une charte pour la nouvelle colonie de Rhode Island. Il a également écrit un dictionnaire de la langue narragansett, Keys to the Indian Language (« clés de la langue indienne »), qui a été publié en Angleterre en 1643.