W 999 roku, podczas drugiej kampanii włoskiej, Herybert został wybrany na arcybiskupa Kolonii, otrzymując z rąk Ottona regalia Kolonii oznaczające jej suwerenne prawa w tym kraju. Sakrę biskupią otrzymał na Boże Narodzenie w kolońskiej katedrze. W tym samym roku wybierano papieża. Został nim Sylwester II, który w Benewento wręczył paliusz Herybertowi. Duchową powierniczką i doradczynią została św. Adelajda z Vilich, która była przeoryszą w kolońskim opactwie Panny Marii na Kapitolu od 1002 roku.
W tym samym roku, wezwany przez Ottona III na zamek Paterno w Falerii (płn. Lacjum,) Herybert był przy śmierci cesarza, a jego relikwie przewiózł do Akwizgranu. W trakcie podróży z doczesnymi szczątkami byłego władcy został zatrzymany i uwięziony przez frankijskiego króla Henryka II, późniejszego władcę Królestwa Wschodnich FrankówWedług tradycji Henryk II przyjechał do Kolonii przeprosić Heryberta za ten incydent (za niem. źródłem).. Mimo napiętych relacji, jakie pomiędzy nimi panowały, towarzyszył nowemu królowi Włoch do Rzymu w 1004 roku. W 1007 roku był sponsorem nowej diecezji w Bambergu, którą powołał Henryk II (późniejszy święty).