Каллистрат был родом из Карфагена. Дед его, по имени Неоскор, служил в Палестине во времена императора Тиверия — под началом Понтия Пилата, прокуратора Иудеи, — и своими глазами видел крестные страдания, смерть и Воскресение Христа. Отец Каллистрата был христианином и воспитал сына в вере и благочестии.

Как и отец, Каллистрат стал воином. Среди сослуживцев-язычников он выделялся кротким нравом и добрым поведением, а по ночам, когда все спали, вставал на молитву. Однажды спавший рядом воин услышал, как он призывает имя Господа Иисуса Христа, и донёс военачальнику.

На допросе Каллистрат наотрез отказался принести жертву идолам. Его избили, потом волочили по острым камням, но сломить не смогли. Тогда военачальник велел зашить его в кожаный мешок и утопить в море. Мешок наткнулся на острый камень и разорвался, а самого мученика, по слову источника, поддержали дельфины, и он вышел на сушу невредимым. Увидев такое чудо, сорок девять воинов уверовали во Христа.

Всех их бросили в темницу, и там Каллистрат продолжал проповедовать и укреплять товарищей к предстоящему подвигу. На новом допросе они твёрдо исповедали веру; тогда им связали руки и ноги и бросили в пруд. Узы распались сами, мученики стояли в воде со светлыми лицами, над их головами был виден светлый венец, и все услышали голос, звавший Каллистрата со стадом его на покой в вечных обителях. В тот же миг дрогнула земля и разбился стоявший неподалёку идол. После этого уверовали ещё сто тридцать пять воинов.

Военачальник побоялся возмущения в войске и судить новообращённых не стал, а Каллистрата с дружиной снова заключил в темницу, где они молились и благодарили Бога за данные им силы. Ночью, по его приказу, мучеников убили мечами. Оставшиеся в живых сто тридцать пять воинов похоронили их останки, а позже на месте страдания — как и предсказывал святой — была сооружена церковь.

Мучеников-воинов на иконах принято писать в воинской одежде, с крестом в руке. Память святого Каллистрата и дружины его совершается 10 октября.