Los orígenes de la Hermandad se remontan a mediados de la década de 1940, en un contexto de profunda devoción popular, resurgiendo de la religiosidad penitencial en la ciudad de Ceuta. Por aquellos años, la imagen de la Dolorosa venerada en la Iglesia de San Francisco, bajo la advocación de María Santísima de las Penas, realizaba salidas penitenciales acompañando en un primer momento a Nuestro Padre Jesús Nazareno y, posteriormente, al Santísimo Cristo de la Expiración.

Será en la primavera de 1945 cuando un grupo de ceutíes, movidos por su fervor y por el deseo de rendir culto público a las sagradas imágenes vinculadas al templo franciscano, comiencen a dar forma a la idea de construir una Hermandad propia. Dichas reuniones tenían lugar en la sastrería de Elena Tresilló, situada en la calle Camoens, que se convertía en la primera y humilde Casa de Hermandad improvisada, y auténtico germen de la corporación.

En sus primeros años, la Hermandad realizaba sus salidas penitenciales venerando como titular a un crucificado propiedad de la Iglesia de San Francisco, al que se le otorgó la advocación de Santísimo Cristo del Perdón y la Misericordia. Paralelamente, la devoción a la Virgen de las Penas fue creciendo, hasta que en 1946 se produjo la primera procesión de la Dolorosa bajo esta advocación, consolidando su papel central dentro de la corporación.

El 26 de abril de 1947 marcaría un hito fundamental en la historia de la Hermandad, al ser aprobadas sus primeras Reglas por el Prelado de la Diócesis, D. Tomás Gutiérrez Díez. Desde ese momento, la corporación pasaba a ostentar oficialmente el título de Fervorosa Hermandad de Penitencia y Cofradía de Nazarenos del Santísimo Cristo de la Humildad y Paciencia y Nuestra Señora de las Penas, quedando fijado el Jueves Santo como día de su salida procesional. Como curiosidad de la época, se estableció entonces la limosna de hermano en una peseta.

En 1948, la Hermandad efectuó su salida procesional acompañando nuevamente a Jesús Nazareno, realizando ambos el tradicional Encuentro en la calle Victori Goñalóns. Un año después, en 1949, la corporación realizó lo que puede considerarse su primera salida penitencial en solitario, asentando definitivamente su identidad propia dentro de la Semana Santa ceutí.

Desde sus inicios, la Hermandad tuvo clara la intención de adquirir una imagen que representara el pasaje del Ecce-Homo, motivo por el cual se incorporaron al escudo corporativo la corona de espinas y la caña a modo de cetro, símbolos inequívocos de la burla sufrida por Cristo. A estos se añadieron los atributos de San Agustín, reflejo de la estrecha vinculación que la Hermandad mantuvo desde el principio con la Orden Agustiniana. Asimismo, se estableció una relación de patronazgo con el Arma de Aviación, con sede entonces en Tetuán, lo que motivó que la Dolorosa recibiera temporalmente la advocación de Loreto, patrona de dicho cuerpo. Aunque esta titulación se perdería con el tiempo, la relación con el ámbito militar se mantendría durante décadas, pasando posteriormente al patronazgo del Regimiento de Infantería de Ceuta nº 54, las Fuerzas Regulares.

A finales de la década de los cincuenta y comienzos de los años sesenta, comenzó a evidenciarse una incoherencia entre la advocación de Humildad y Paciencia y la iconografía del Cristo Crucificado que veneraba la Hermandad. Ante esta circunstancia, se planteó la necesidad de sustituir la imagen por otra que representara de forma más fiel el momento pasional que se deseaba mostrar.

Por recomendación de Guerra Artiel, el Cabildo de Oficiales decidió encargar una nueva imagen al taller valenciano del imaginero José Rabasa Pérez. Tras un periodo de deliberación, la Junta de Gobierno optó por una imagen de Ecce-Homo, concebida para procesionar en solitario, con el Señor ya coronado de espinas y portando la caña como cetro, una vez consumada la burla. Se cree que la imagen del titular cristífero de la Hermandad de los Estudiantes de Málaga pudo servir como inspiración, si bien no existe constancia documental que lo confirme.

En el verano de 1960, la imagen del Santísimo Cristo de la Humildad y Paciencia ya figuraba entre los encargos del taller de Rabasa Pérez, como acreditan los pagos realizados: una primera entrega de 9.000 pesetas el 31 de julio de ese año, seguida de otra cantidad idéntica el 14 de febrero de 1961. El 21 de marzo de 1961, la imagen fue trasladada a Ceuta por operarios de la Agencia Partida, realizándose el último pago, por importe de 11.515 pesetas, el 31 de julio de 1961. El coste total ascendió a 29.515 pesetas, abonadas incluso después de la llegada de la imagen a la Hermandad.

En 1968 se produjo otro hecho significativo con la creación de la primera cuadrilla de hermanos costaleros, formada por estudiantes del Colegio San Agustín, que decidieron portar sobre sus hombros el paso del Señor.

Durante los mediados de la década de los ochenta, la Hermandad estrenó un nuevo paso procesional para el Santísimo Cristo de la Humildad y Paciencia, dotando a la estación de penitencia una mayor prestancia estética y acorde con los cánones artísticos del momento.

En 1983, la imagen de Nuestra Señora de las Penas fue sometida a una importante restauración, encomendada al imaginero sevillano Luis Álvarez Duarte, tras su participación en un acto celebrado por la Hermandad el 28 de junio de ese mismo año. El coste de la intervención ascendió a 250.000 pesetas. Durante el proceso, el imaginero descubrió las iniciales B.M., lo que, unido al estudio estilístico y el análisis de las maderas, le llevó a atribuir la autoría de la imagen al escultor valenciano Blas Molner, fallecido en 1812.

Entre 1986 y 1987, se consideró oportuno acometer una restauración del Santísimo Cristo de la Humildad y Paciencia para adecuarlo al contexto neobarroco que había adquirido al procesionar en su nuevo paso. Tras un exhaustivo reconocimiento realizado por el tallista ceutí Ángel Lillo, se determinó la viabilidad de la intervención, que fue finalmente confiada al profesor Juan Manuel Miñarro López. El 13 de noviembre de 1986, la imagen fue trasladada a Sevilla con el consentimiento de la Vicaría de Ceuta y los Padres Agustinos, firmándose ese mismo día el contrato de restauración. La intervención incluía tanto la restauración como la transformación pictórica de la imagen, con vistas a su entrega antes de los cultos de 1987, por importe total de 300.000 pesetas.

 Cabe destacar que, tanto Miñarro como otros artistas consultados, se negaron a intervenir el paño de pureza que cubre las piernas del Señor, permaneciendo inalterado hasta la actualidad.

En 1989, la Hermandad aprobó sus nuevas Reglas, adaptándose a los nuevos tiempos sin perder su esencia fundacional. Posteriormente, en 1995, un Cabildo General Extraordinario acordó la modificación de la túnica nazarena, introduciendo cambios significativos en la estética penitencial.

Finalmente, en 1997, con motivo del Cincuenta Aniversario de la aprobación de las primeras Reglas, la Hermandad celebró diversos actos conmemorativos, entre los que destacaron un pregón, un concierto de la Banda Municipal y una comida de hermandad. El broche de oro a estas celebraciones tuvo lugar el 4 de octubre, con la salida procesional extraordinaria de Nuestra Señora de las Penas, que quedaría grabada para siempre en la memoria de los hermanos y de la ciudad.