Fregatten Josephine byggdes mellan 1831 och 1834, ritad av Borneman. Hon var bestyckad med fyra bombkanoner och 32 tjugofyrapundiga kanoner. Dessutom höll hon båtkanoner om två enpundskanoner och två tolvpundiga karronader.
Efter fransmännens erövrande av Alger 1830, var Marocko den enda av de sjörövande så kallade Barbareskstaterna som fortfarande krävde tributer från mindre sjöfartsnationer såsom Sverige för att svenska flottans skepp skulle få segla obehindrat i Medelhavet. Därför avsändes bland andra fregatten Josephine till dessa farvatten under kommendörkapten Gyllengranat år 1837 för att ordna mer bestämda avtal med Marocko. Eskadern seglade sedan vidare till den grekiska ön Korfu, för att återkomma till Karlskrona i juli 1838.
De förödmjukande tributerna upphörde för Skandinaviens del sedan ett fördrag slutits i marockanska Larache i april 1845. Josephine hade sänts dit i oktober året innan, där kommendörkapten Karl Ulner och generalkonsul Ehrenhoff återupptog de underhandlingar med sultanen som tidigare blivit avbrutna. Josephine återvände när de lyckade förhandlingarna var i hamn.
Under en preliminär fred under dansk-tyska kriget 1848-1850 kom parterna bland annat överens om att 4 000 svensk-norska trupper skulle besitta norra Slesvig. Dessa trupper överfördes av Josephine tillsammans med fregatten Eugenie, ångkorvetten Thor och ångfartyget Gylfe.
Några år senare, 1860, gjorde Josephine en expedition till Norge, där hon bevistade kung Karl XV:s kröning i Trondheim.
År 1868 byggdes Josephine om till korvett och året därpå, 1869, utförde hon djuplodningar mellan Portugals kust och Azorerna. Strax väster om Kap Sankt Vincent upptäcktes en minst 100 famnar (178 meter) djup bank, som sedan dess kommit att kallas "Josephines bank".