Paulus Stephanus Cassel wurde als Sohn eines jüdischen Bildhauers geboren. Sein ursprünglicher Vorname lautete Selig. Cassel absolvierte das Gymnasium in Schweidnitz und studierte anschließend Geschichtswissenschaft an der Berliner Universität, wo er unter anderem die Vorlesungen von Leopold Ranke hörte.
1849 gab er als überzeugter Royalist in Erfurt zunächst die Constitutionelle Zeitung heraus und später – von 1850 bis 1856 – die Erfurter Zeitung. Am 28. Mai 1855 empfing er in der evangelischen KircheBüßleben bei Erfurt die christliche Taufe. Er wurde anschließend Bibliothekar der Königlichen Erfurter Bibliothek. Ein Jahr später avancierte er zum Sekretär der Erfurter Akademie und erhielt aufgrund seiner königstreuen Einstellung und Arbeit von Friedrich Wilhelm IV. den Titel eines Professors.
Um 1860 hatte er in Berlin für kurze Zeit die Stelle eines Gymnasiallehrers inne, wirkte aber vor allem als freier Schriftsteller. In den Jahren 1866 und 1867 wurde er als Mitglied der Konservativen Partei in das Preußische Abgeordnetenhaus gewählt.
Um 1867 kam Cassel in Kontakt mit der Londoner Gesellschaft zur Verbreitung des Christentums unter den Juden, die ihn als Reiseprediger anstellte. Gleichzeitig übernahm er die Aufgaben eines Pastors an der freikirchlich orientierten Christuskirche in Berlin. Hier machte er auch auf den jungen Adolf Damaschke, den späteren Pädagogen und Bodenreformer, einen bleibenden Eindruck.
Galt seine theologische Arbeit in der ersten Phase seines 24-jährigen pastoralen Dienstes vor allem der Judenmission, so kämpfte er in den letzten Jahren seines Lebens verstärkt gegen den aufflammenden Antisemitismus des späten 19. Jahrhunderts an.
1872 erhielt Cassel die Ehrendoktorwürde durch die Universität Wien.
Cassels Bruder David wirkte als Dozent an der Berliner Hochschule für die Wissenschaft des Judenthums.