A principios de 1953 surgió la atractiva y apropiadísima idea de fundar una hermandad del Cristo de los Navegantes con sede en la recientemente creada parroquia de la Inmaculada Concepción (cuya jurisdicción comprendía el marinero barrio de la Casería de Ossio y la población naval militar de San Carlos) con el ánimo encomiable de agrupar y hermanar a marinos de guerra, pescadores, gentes de la mar en definitiva, y con la finalidad social de atender a los pobres el barrio.
La naciente Cofradía de los Navegantes decidió dar culto a Jesús Crucificado bajo ese título, saliendo en procesión en la madrugada del Viernes Santo, rezando las catorce estaciones del Vía Crucis y llevando a la imagen titular sobre un modesto paso sin más acompañamiento musical que un par de tambores marcando el ritmo. En el origen de esta cofradía también influyó el prototipo severo y ejemplar de la Hermandad de la Vera Cruz, que antaño había sido también hermandad gremial de los navegantes y cuyos estatutos sirvieron de modelo a aquella.
La cofradía fue erigida canónicamente y aprobados sus estatutos en mayo de 1953, siendo elegido Manuel Quijano Párraga como primer hermano mayor. En el entretanto se había decidido modificar la advocación primitiva del titular así como el día de salida, aunque permaneció la idea básica de que la salida procesional consistiera en el rezo del Vía Crucis por las calles de la feligresía. Nació entonces la cofradía de penitencia del Santísimo Cristo del Perdón.
En julio de ese mismo año se encargó la imagen titular al escultor isleño Antonio Bey Olvera, quien la entregó ocho meses después. El Cristo del Perdón fue bendecido el 21 de marzo de 1954, al mismo tiempo que un nuevo altar lateral donde sería colocado a la veneración de los fieles. La corporación también dispuso en sus primeros años de un local social en la calle San Roque de su apartado barrio.
La Cofradía salió por vez primera en la tarde del Jueves Santo de 1954, rezando las estaciones del Vía Crucis, según lo previsto en sus reglas, y llegando hasta la calle San José y San Antonio. Al año siguiente amplió su recorrido hasta la calle Ancha, itinerario éste que mantuvo ya durante décadas. En 1956 retomó la idea original de salir el Viernes Santo, aunque por la tarde, haciéndolo así durante unos pocos años, hasta que volvió de nuevo al Jueves Santo. Desde el principio, sus penitentes (siempre de riguroso hábito negro y cíngulo blanco) se distinguieron por salir portando grandes rosarios y unas características cruces en lugar de cirios.
Por espacio de un cuarto de siglo la hermandad mantuvo su estilo ascético, sobrio y sus peculiaridades distintivas: vía crucis procesional, cruces en lugar de cirios, e itinerario sólo hasta la calle Ancha, sin llegar a pasar por la carrera oficial como el resto de las cofradías, en razón de la lejanía de su barrio del centro de la ciudad.
Tras pasar por una crisis en la década de 1970, la Hermandad se ha consolidó y al propio tiempo evolucionó y emprendió una serie de novedosas y valientes reformas: en 1983 llegó por primera vez a la carrera oficial, en el centro de la ciudad, haciéndolo desde entonces ininterrumpidamente bien que a través de diversos itinerarios; en 1985 fue bendecida la imagen de la Virgen de la Paz, cotitular de la asociación, que todavía no procesiona; en 1994 estrenó un magnífico paso neobarroco; en 1997 decidió llevar tras el paso una agrupación musical, prescindiendo del tradicional y sobrio ritmo de tambores, etc.
Pero estas innovaciones las ha conjugado acertadamente con las raíces que determinaron su fundación y los pilares que sostuvieron su historia: espíritu austero, rezo de las estaciones del vía crucis durante la procesión, vínculos con las gentes y profesionales de la mar (ejemplificado en el nombramiento del Tercio del Sur de Infantería de Marina como hermano honorario) y compromiso social con su periférico barrio.