The location of Phoulloi remains unknown, and a subject of differing opinions among historians. Proposed identifications with modern settlements include Solkhat and Tepsen in the eastern part of the Crimea, as well as Chufut-Kale and Kyz Kermen near Bakhchysarai in the western part of the peninsula. According to O. Pritsak in the Oxford Dictionary of Byzantium, "it was probably located on the trans-Crimean route, approximately halfway between Cherson and Cimmerian Bosporos".
The city is first mentioned by the 6th-century Byzantine historian Menander Protector. It occurs next in the hagiography of the late 8th-century saint John of Gothia, who was held prisoner in the city in 787, and baptized and cured the child of the local lord, before escaping to Amastris. In the 9th century, the hagiography of Constantine the Philosopher mentions the "nation of Phoulloi", who venerated an oak tree and were ruled by an elder.
The Notitiae Episcopatuum of the Patriarchate of Constantinople in the late 8th and 9th centuries record that the bishop of the Khazars (Chotziroi) resided near Phoulloi and another place with the Turkic name Kara Su ("Black Water"), hellenized as Charasion (Χαράσιον) or translated as Mabron Neron (Μάβρον Νερὸν) in the Notitiae. In subsequent Notitiae, Phoulloi itself appears as the sea of an archbishop. By the 14th century, the local see had been merged with that of Sougdaia, and a metropolitan bishopric of Sougdaia and Phoulloi is well attested in 14th–15th century documents. The fate of the city after that is unknown.
- Pritsak 1991, p. 1670.