Se desconoce el año de fundación exacto del Theodorianum, si bien su creación seguramente estuvo ligada a la recién construida catedral de Paderborn (el edificio original, inaugurado en 777), a la que se sabe que se adjuntó un monasterio que a partir de 780 servía como centro misionero.^[5]​ Se ha considerado al año 799 como el momento de su fundación, coincidiendo con la creación de la arquidiócesis de Paderborn bajo los auspicios de Carlomagno.^[1]​ La llegada del papa León III a la catedral para el acto de iniciación fue acompañada como de costumbre por una donación al monasterio por parte del todavía rey de los francos (y futuro sacro emperador romano), que muy probable incluía, como también de costumbre, una escuela catedralicia (Carlomagno había ordenado establecer escuelas en todas las catedrales de los territorios ganados a los sajones, vistas por él como necesarias para la divulgación de la fe). Sobre la ubicación de la escuela se sabe que a mediados del siglo IX, bajo el obispado de Badurado (segundo obispo de Paderborn), se encontraba algo al norte del antiguo Karlsburg (Urbs Karoli), y más tarde (como mínimo desde comienzos del II milenio), ya durante el obispado de Meinwerk, al oeste de la misma (en todo caso queda patente que se encontraba en las inmediaciones de dicha residencia imperial ya desde sus inicios).

En esa época el instituto tuvo entre su profesorado a algunos personajes destacados en la historia de la región. Su primer director en la época del obispo Meinwerk fue Altmano de Passau, quien más tarde destacaría como obispo de Passau y preboste de Aquisgrán, localmente venerado como santo. Unas décadas más tarde, a principios del siglo XII, la escuela alcanzaría especial relevancia debido al trabajo del deán catedralicio y computista Reinher de Paderborn (magister scholarum en el instituto y luego su rector; praefectus scholae), con la publicación en 1171 del Computus emendatus, obra que más allá de presentar una mejora en el cálculo de la fecha de la Pascua, fue la primera en utilizar el sistema decimal indo-árabe en Europa Occidental. Gran parte de su trabajo, que en su día le valió las calificaciones de «el reformador del calendario» y «maestro de la aritmética moderna», lo realizó en su despacho en la escuela catedralicia de Paderborn. Casualmente, la publicación de la obra coincidió con el nacimiento de otro futuro rector del instituto, Óliver de Paderborn, quien un siglo más tarde sería obispo de la diócesis y luego cardenal obispo de Sabina, famoso por sus viajes y por su papel de predicador, combatiente y prolífero cronista durante las Cruzadas.

A comienzos de la Edad Moderna, la expansión de las universidades en Europa (una institución surgida ya durante el Renacimiento del siglo XII) supuso el comienzo de la decadencia de las escuelas cardenalicias, que afectó también a la escuela de Paderborn.^[2]​ Si bien, como otras instituciones de su estatus, logró renovarse a principios del siglo XVI adaptándose a la corriente humanística de la época, combinando los estudios clásicos con un currículo moderno. Es cuando Salentín de Isemburgo, príncipe-obispo de Paderborn (soberano electo del principado episcopal homónimo), establece nuevos estándares pedagógicos para la institución bajo dirección de Hermann Kerssenbroich (luego Hermann von Kerssenbrock), quien sería más conocido por su rectoría del Gymnasium Carolinum, en Osnabrück. En su época, las operaciones del instituto, que pasó a nombrarse Gymnasium Salentinianum a nombre de su benefactor, se agilizaron y modernizaron en gran medida.^[2]​ Los últimos años de la década de 1570 fueron teológicamente significantes en esa región por la difusión del protestantismo. Debido a las sensibilidades religiosas y algunas acusaciones en su contra, en 1577 Salentín renunció a sus cargos de príncipe-obispo de Paderborn y príncipe elector de Colonia, quedando como conde de Isemburgo-Grenzau (título hereditario en una región cuya inmediación imperial él mismo había propugnado años atrás). Su sucesor, Enrique de Sajonia-Lauenburgo, se convertiría al luteranismo, al igual que toda la comunidad de Paderborn (incluyendo al profesorado de la escuela y su dirección, posterior a Kerssenbrock, quien ya se encontraba en Osnabrück).^[1]​

Sin embargo, la contrarreforma, presente en Paderborn desde 1580, tuvo un impacto sobre el gymnasium ya desde sus comienzos de la mano de los jesuitas,^[6]​ impulsados por Pedro Canisio (posteriormente santificado), quien entendía el papel de las instituciones de enseñanza mayor en la difusión de una doctrina en la sociedad. Los jesuitas westfalianos (que aún estaban obligados a vestir el hábito secular, aunque ya se les permitía la divulgación de textos católicos) irían ejerciendo una influencia cada vez mayor en la «recatolización» del instituto, introduciendo gradualmente elementos pedagógicos de contenido y fondo católico reformista. El 1 de mayo de 1585 asumieron plenamente la dirección del Salentinianum, el cual, de acuerdo con fuentes contemporáneas, pese a la hostilidad de la ciudadanía anticatólica de Paderborn, experimentó un notable crecimiento en los años siguientes, pasando de 140 a más de 400 alumnos solo en el primer año. Llevando a la práctica la teoría de Canisio, aquello supuso el comienzo de la contrarreforma en la capital diocesana. Tras la elección del implacable Teodoro de Fürstenberg (Dietrich von Fürstenberg) como príncipe-obispo con el nombre Teodoro IV, este puso en práctica una agresiva política dirigida a la erradicación del protestantismo en Paderborn, proceso que culminaría en 1604 tras algunos episodios violentos entre ambas confesiones.

En 1595 comenzó el proceso de separación del gymnasium del recinto de la catedral. A tal fin se construyó un nuevo edificio jesuita en los terrenos de un cercano monasterio de franciscanos conventuales, inaugurado en 1609, al que se trasladaron la mayoría de las clases.^[5]​ Un aula permaneció en el claustro de la catedral, que serviría como escuela catedralicia por dos siglos más (hasta 1804). El 31 de julio de 1612, Teodoro, ahora de los príncipes-obispos alemanes más incluyentes, colocó la primera piedra del edificio de estudios, que sigue existiendo activo hasta la actualidad (siendo actualmente el ala transversal unido a la torre del edificio).^[6]​ A la hora de su construcción, el elemento arquitectónico más destacado era su torre occidental (una torre adicional, en el ala oriental, sería añadida solo en el siglo XVIII).^[2]​ En 1614, la escuela, ahora llamada Akademisches Gymnasium (‘gimnasio académico’) o Theodorianisches Gymnasium, en honor a Teodoro (cuyo nombre sigue llevando en la actualidad), se trasladó al nuevo edificio, que aún sirve al instituto a día de hoy (tras una amplia reconstrucción en la década de 1950). Encima de la entrada principal se conserva la inscripción COLLEGIVM SOCIETATIS IESV, una referencia al pasado jesuita de la escuela. La inauguración de la nueva instalación se considera también el momento de fundación de la primera universidad westfaliana, la Academia Theodoriana^[7]​ (conocida también como la Universidad Jesuita^[2]​) —actual Facultad de Teología de Paderborn—, que compartía el mismo complejo de edificios. La emblemática escalinata de la facultad fue donada por el preboste de la catedral, Walther von Brabeck, y su deán, Arnold von Horst, ese mismo año.^[5]​

La devastadora guerra de los Treinta Años dejó una huella en la ciudad, sobre todo tras el arrasador ataque en 1646 por tropas hesianas y suecas al mando de Carl Gustaf Wrangel (recién nombrado mariscal de campo), en la que se tiene constancia del uso del recinto del gymnasium a fines militares, probablemente como lugar de acopio de armas y provisiones del bando católico.^[8]​ En esta época, el poeta jesuita Friedrich Spee, objetor de los juicios de brujería, enseñaba teología en el edificio (en el marco de la Universidad Jesuita). Acabada la guerra —y manteniéndose el catolicismo en el pequeño Estado imperial de Paderborn—, el instituto, al igual que toda la región, experimentó un período de florecimiento barroco que aumentó su prestigio, llegando a ser de los mayores centros de enseñanza de la región, con un número de alumnos que en ocasiones rozaba el millar. Su área de influencia no se limitaba al obispado de Paderborn, sino que se extendía también a los vecinos ducado de Westfalia y obispado de Münster. Gracias a los planes de estudios jesuitas, ahora unificados, fue de los principales integrantes de una red educativa católica europea, fomentada por el Sacro Imperio Romano. En ese tiempo se produce otro importante cambio debido a la influencia jesuita: la apertura de la escuela a las clases medias y bajas, que en un punto llegarían a representar cerca del 70 % del alumnado (en una época en la que los estudios académicos aún se reservaban principalmente a las clases altas). En esa época, el mayor impulsor y benefactor del gymnasium fue el príncipe-obispo Fernando II de Paderborn, quien mandó construir la iglesia universitaria barroca que, siendo actualmente uno de los monumentos históricos de la plaza del Ayuntamiento (conocida como la iglesia del Mercado, Marktkirche), sigue siendo a día de hoy lugar de congregación de los alumnos y profesorado del instituto.^[8]​

A principios del siglo XVIII, el Theodorianum aún era destino atractivo para alumnos de toda Westfalia, como fue el caso del arquitecto y maestro del barroco Johann Conrad Schlaun.^[2]​ Aquello requería una ampliación de su espacio, por lo que arquitectónicamente, es cuando se añaden algunos de los elementos del edificio que lo caracterizan, concretamente la adición de la torre oriental (1729) y la construcción del ala sur que conecta con la iglesia jesuita (1730-1734).^[2]​ Si bien, a mediados del siglo comienza un declive en su importancia a la par con los problemas internos en el Sacro Imperio, manifestados por un distanciamiento de los príncipes territoriales. Esta crisis se agudizó aun más con la supresión de la orden jesuita en 1773 por el papa Clemente XIV, momento en que la escuela se vio obligada a «independizarse». Aunque miembros de esa orden seguían extraoficialmente en una comunidad cercana parecida a un monasterio, habían perdido su influencia, con lo que ya no podían atraer a un gran número de alumnos de otros territorios. También contribuyó al proceso el clima social en gran parte de Westfalia, cada vez más atraído hacia la Ilustración a costa de la educación en un marco pedagógico de carácter religioso.

Tras la ocupación del principado de Paderborn en 1802 por el Reino de Prusia, la dirección de la escuela fue asumida por la nueva administración, resultando en su conversión en un gymnasium neohumanista (calificación que recibe en Alemania el movimiento humanista posrrenacentista).^[8]​ Se admitió de nuevo a estudiantes protestantes, y por primera vez a judíos. También en el marco del napoleónico Reino de Westfalia (1807-1813) se mantuvo esta tendencia, si bien en algunos ámbitos de las nuevas enseñanzas, especialmente las lenguas modernas, el instituto de orientación clásica quedó atrás. Tras la anexión definitiva del principado por Prusia, el Akademisches Gymnasium (nombre único de la escuela en esos años) pasó a depender del recién establecido Real Consistorio (Königliches Konsistorium) de la nueva provincia de Westfalia y más tarde, en 1825, de la junta escolar provincial de Münster (Provinzialschulkollegium). Las enseñanzas basadas en el neohumanismo se consolidaron con la implantación de la reforma humboldtiana en la educación prusiana.^[9]​ En 1821 se llevó a cabo el primer examen de Abitur (bachillerato) para alumnos del gymnasium, confirmando su condición de instituto superior de enseñanza secundaria. En 1846 su nombre recuperó la referencia al antiguo promotor de su emblemático edificio, pasando a llamarse Gymnasium Theodorianum, su nombre actual (durante el período del Imperio alemán, se añadía el adjetivo «Real»: Königliches Gymnasium Theodorianum).^[10]​

La Revolución alemana de 1848-1849 pasó en su mayor parte sin altercados en el Theodorianum, salvo un episodio en diciembre de 1848, cuando el jurista Franz Löher, exalumno del instituto y entonces pasante en el Tribunal Regional Superior, fue arrestado después de llamar a la huelga impositiva (Steuerstreik) en una publicación de su periódico, el Westfälische Zeitung. Su detención provocó disturbios en el gymnasium, aunque por poco tiempo.^[8]​ En los siguientes años volvió a aumentar el número de alumnos del instituto constantemente hasta superar el medio millar, aunque en la segunda mitad del siglo volvería a caer, principalmente debido a la acreditación con el título de gymnasium de otras dos instituciones westfalianas (una en Brilon y la otra en Warburg).

El 1 de enero de 1874, en virtud de las llamadas Leyes de la Iglesia adoptadas por Prusia el año anterior, el instituto pasó a ser propiedad estatal, marcando su separación de la Iglesia.^[11]​ Si bien, aún no funcionaba como escuela pública, y una petición oficial al respecto fue rechazada por el alcalde de la ciudad en 1882, sobre todo por cuestiones financieras. No obstante, la falta de espacio se hacía notar cada vez más en un edificio que había quedado anticuado,^[5]​ con lo que entre 1887 y 1893 se llevaron a cabo trabajos de renovación y algunas ampliaciones, que confirieron al Theodorianum el aspecto que tendría en el próximo medio siglo, hasta los destrozos sufridos hacia finales de la Segunda Guerra Mundial. Al mismo tiempo, en 1888, se fundó finalmente también una escuela adjunta orientada hacia los estudios prácticos (Bürgerschule), que décadas después se convertiría también en un gymnasium (a nombre de su fundador, el alcalde de la ciudad Reismann). Varios dibujos de finales del siglo y comienzos de los años 1900 muestran un reloj en la planta superior de la torre oriental,^[12]​^[13]​ que podría haber sido parte de la ampliación de la década anterior, si bien no existe en la actualidad (en su lugar hay un ventanal redondo).

A principios del siglo XX, el Theodorianum destacó como una institución patriótica católica en medio de la Prusia predominantemente protestante.^[8]​ Durante las celebraciones del 300.º aniversario del edificio, la ciudad de Paderborn mandó realizar una serie de estatuas, que se colocaron en las ménsulas de las fachadas este y sur del patio.^[14]​ Las figuras incluían a Carlomagno, el emperador Guillermo II y reyes alemanes anteriores bajo cuyo reinado operaba el instituto, así como sus fundadores y obispos de Paderborn. La mayoría de las estatuas se perdieron en los bombardeos aliados, y las que sobrevivieron están en exhibición en el Museo Diocesano del Arzobispado de Paderborn.

Durante los bombardeos de Paderborn del 17 de enero y 27 de marzo de 1945, los edificios del Theodorianum quedaron prácticamente destruidos.^[5]​ La antigua biblioteca escolar, con sus aproximadamente 14 000 libros,^[10]​ se perdió casi en su totalidad.^[15]​ Después de la guerra, se inició una amplia reconstrucción del complejo a partir de modelos históricos, sobre los cimientos que habían sobrevivido los ataques. En la reconstrucción se hizo uso también de piezas originales halladas entre los escombros, como materiales e inscripciones. La ceremonia de inauguración tuvo lugar en 1954. En 1962, la escuela celebró su 350.º aniversario casi recuperada en su totalidad (si bien, la torre occidental, el elemento más destacado del edificio, no recuperaría su chapitel hasta 1975).

• Imágenes del Theodorianum de los años 1920-1930
•  
•  
•  

En 1971, con la introducción de la coeducación, el instituto, que estaba destinado desde sus inicios a alumnos varones, empezó a admitir a alumnas entre sus filas (aunque una clase exclusivamente masculina se mantuvo hasta bien entrada la década de 1990).

A partir de la segunda década del siglo XXI, el enfoque social del Theodorianum se ha centrado en un conjunto de valores desarrollados formalmente por la comunidad escolar, siendo el primer colegio en hacerlo de forma oficial. En 2020, el gymnasium recibió el título de Escuela sin Racismo, un proyecto nacional patrocinado por el exfutbolista y entrenador Steffen Baumgart. En 2019 se realizó una ampliación del exterior del edificio, siendo rediseñado el patio interior, destinado principalmente a alumnos de primera y segunda de la ESO.^[16]​ En cuanto a su plan de estudios, fiel a sus orígenes, este sigue nutriéndose de una tradición humanística; entre otros, el latín sigue siendo una asignatura obligatoria en parte de la fase de educación obligatoria.^[17]​

A continuación una lista parcial de algunos de los graduados más conocidos del Theodorianum: