Según el geógrafo alemán Johann Friedrich Goldbeck (1748-1812), la ciudad originalmente se llamó Brunsberg en honor a Bruno von Schauenburg (1205-1281), obispo de Olomouc en Moravia, quien acompañó al rey Otakar II de Bohemia en 1254 y 1267 cuando este último participó en la cruzada de los Caballeros Teutónicos contra los antiguos prusianos.^[3]​ También se ha sugerido que el nombre Braunsberg podría provenir de Brusebergue ("campamento de los prusianos"), pero esta noción no está documentada.

En 1243, la Orden Teutónica cedió el asentamiento y la región circundante de Varmia al recién creado Principado-Obispado de Varmia, cuyo obispo construyó su catedral en la ciudad y la convirtió en su residencia principal. La ciudad recibió privilegios de ciudad basados en los de Lübeck en 1254, pero en 1261 fue destruida y despoblada durante el segundo Levantamiento Prusiano. Fue reconstruida en una nueva ubicación en 1273 y colonizada por colonos de Lübeck. En 1284, recibió una nueva carta de ciudad, también basada en la de Lübeck. Sin embargo, el siguiente obispo, Heinrich Fleming (1278-1300), trasladó el capítulo de Braunsberg a Frauenburg (actual Frombork).

En 1296 se construyó una abadía franciscana y, en 1342, se añadió una "ciudad nueva". Como la ciudad comercial y portuaria más importante de Varmia, la ciudad prosperó como miembro de la Liga Hanseática, donde permaneció hasta 1608. En 1440, la ciudad fue uno de los miembros fundadores de la Confederación Prusiana, que se oponía al dominio teutónico,^[4]​^[5]​ y a petición del rey Casimiro IV Jagellón incorporó el territorio al Reino de Polonia en 1454. La ciudad juró lealtad al rey polaco y reconoció su dominio en marzo de 1454 en Cracovia.^[6]​ Tras la Guerra de los Trece Años, los Caballeros Teutónicos renunciaron a cualquier derecho sobre la ciudad en la Segunda Paz de Toruń en 1466.^[7]​ Administrativamente, formaba parte del Principado-Obispado de Varmia en la nueva provincia autónoma de la Prusia Real, que posteriormente también formaría parte de la Provincia de la Gran Polonia.

Tras la secularización de la Orden Teutónica en 1525, gran parte de sus habitantes se convirtió al protestantismo luterano. El duque Alberto, que había sido gran maestre de la Orden, intentó unir Varmia con el Ducado de Prusia (un estado vasallo cercano de Polonia), obligando a los católicos de la ciudad a jurar lealtad al rey de Polonia a cambio de ayuda contra la Prusia protestante. En 1526, una comisión real polaca liberó a los burgueses de Braunsberg del juramento al rey polaco y devolvió la ciudad al Príncipe-obispo Mauricio Ferber. Sin embargo, al igual que toda la zona de Varmia, Braunsberg juró lealtad a los príncipe-obispo de Varmia, súbditos de los papas. Además, tuvo que renunciar a todas las enseñanzas luteranas y entregar los escritos luteranos. A partir de entonces, Warmia siguió siendo predominantemente católica (incluso después de la Partición de Polonia, cuando pasó a formar parte de Prusia en 1772).

Braniewo estuvo ocupada por Suecia durante unos tres años durante la Guerra de livonia en el siglo XVI. En Varmia, las enseñanzas luteranas fueron reprimidas de nuevo cuando el príncipe-obispo Stanisław Hozjusz (1504-1579) trajo a los jesuitas y fundó el colegio Collegium Hosianum. Entre los estudiantes del colegio se encontraban el católico polaco San Andrés Bobola, los estadistas y altos dignatarios polacos Mikołaj Zebrzydowski^[8]​ y Piotr Gembicki, el poeta latino más destacado de Europa del siglo XVII, Maciej Kazimierz Sarbiewski,^[9]​ el misionero, explorador, matemático, astrónomo y sinólogo Jan Mikołaj Smogulecki,^[10]​ y el primado de Polonia Gabriel Podoski.^[11]​ El destacado poeta renacentista húngaro Bálint Balassi residió en la ciudad entre 1590 y 1591.^[12]​ En 1564 se añadió un seminario sacerdotal. Posteriormente, el papa Gregorio XIII añadió un seminario de misiones papales para los países del norte y este de Europa. Regina Protmann (1552-1613), originaria de Braunsberg (Braniewo), fundó la Orden de Santa Catalina en la ciudad, reconocida por la iglesia en 1583. El teólogo jesuita Antonio Possevinus contribuyó decisivamente a la ampliación del Collegium Hosianum en la década de 1580 para contrarrestar el creciente movimiento protestante.