La création du diocèse par la constitution apostoliqueEpiscoporum Poloniae coetus, promulguée par le pape Paul VI le , renoue avec la tradition de l'éphémère diocèse médiéval de Kołobrzeg. Fondé au congrès de Gniezno en 1000, cet évêché était soumis sous l'autorité de l'archidiocèse de Gniezno. Il ne compta jamais qu'un seul évêque, Reinbern, un noble de Saxe qui était nommé avec l'accord de l'empereur Otton III et le duc Boleslas Ier de Pologne. Le premier évêque catholique en Poméranie, il fait démolir les sanctuaires païens mais il est chassé par un soulèvement des tribus slaves quelques ans après.