Наиболее древние части Голштинских ворот сохранены около берегов реки. Неизвестно, когда именно на этом месте появились первые ворота, которые предоставляли возможность выйти из города в этом направлении. Голштинский мост впервые упоминается в 1216-ом году. Затем следующее упоминание о Голштинских воротах датируется 1376-ым годом. В это время ворота были построены из дерева. Этим же периодом датируются деревянные макеты города Любек Элии Дибеля. По ним можно определить, что ворота включали прямоугольную башню с деревянной галереей в верхней части строения.

Неизвестно когда именно, но не позднее 17-ого столетия Внутренние Голштинские ворота были заменены на меньшие по размеру ворота с двойными воротами. Возможно, это решение были спровоцировано тем, что больше город не нуждался в больших по размеру укрепленных воротах. Двойные ворота в свою очередь были заменены на простые железные ворота в 1794-ом году, которые были уничтожены в 1828-ом году. Вероятно, что существовали также ворота на противоположной стороне реки, но неизвестно, как они выглядели. Скорее всего, они были уничтожены до строительства Средних Голштинских ворот.

В 15-ом столетии ворота, как общепринято считать, были модифицированы в связи с развитием огнестрельного оружия. В этот период потребовалось более сильное укрепление ворот и крепостных стен. Было решено построить другие ворота – Внешние Голштинские ворота, которые позже стали известны как Средние Голштинские ворота, а сегодня мы именно их называет Голштинские ворота Любека.

Строительство этих ворот было оплачено членом городского совета Иоганном Бролингом, который выделил 4000 марок на строительство Средних Голштинских ворот. В 1464-ом году архитектор Генрих Хелмстед начал строительство ворот, которое было закончено в 1478-ом году. Ворота были построены на семиметровом холме. Уже во время строительства стало известно, что фундамент неустойчив. Южная башня осела из-за болотистого грунта на стадии строительства, и в последующее время строители пытались как-то поддержать башню и не дать ей разрушиться.