Польский князь Болеслав Храбрый, которого возвысила дружба Оттона III, вторгся в незащищенное маркграфство Эккехарда и дошел до Мейсена. Тем не менее он появился в Мерзебурге среди приносивших клятву верности саксонских князей и был пожалован в качестве ленов Землей мильценов (мильчан) и Лаузицем, то есть восточными половинами маркграфства Мейсен и саксонской Восточной марки. Мейсен, за который он предложил королю большие деньги, получил его родственник Гунцелин. Вероятно, то была попытка Генриха сохранить дружественные отношения с Польшей, поскольку он — пока еще даже не властелин над всеми германскими племенами — был не в состоянии возвратить герцога в старые границы Польши по Бубру и Квейсу. Когда Болеслав покидал пфальц, он со своей свитой, без ведома короля, подвергся нападению. В ответ на это он сжег Штрелу (севернее Мейсена) и вернулся в свою страну с большим числом пленных.
В Богемии был свергнут неспособный управлять Болеслав III Рыжий и возвысился поляк Владивой, который присягнул Генриху на верность в ноябре 1002 года в Регенсбурге. Его смерть в следующем году побудила Болеслава Храброго вновь содействовать приходу к власти Болеслава Рыжего — только для того, чтобы использовать его бездарность и жестокость в качестве повода вновь вмещаться в богемские дела. Он взял Прагу и пожизненно заключил Болеслава Рыжего под стражу. Сознавая свою власть, которая простиралась от Балтийского моря до Карпат и от Вислы до Богемского Леса (Моравию он также подчинил), Болеслав Храбрый отказал королю Генриху в клятве верности от Богемии. Он нашел себе союзников в лице Генриха фон Швейнфурта, который считал себя обманутым баварцами, его двоюродного брата, Бабенберга Эрнста, и брата короля Бруно. В этой труднейшей ситуации Генрих заключил союз с язычниками редариями и другими племенами объединения лютичей, старых врагов Польши, которых не смог покорить Оттон III.
Вскоре король совладал с мятежом в Нордгау и Франконии. Маркграф Генрих после непродолжительного заключения получил назад свой аллод в районе Швейнфурта и маркграфство, но лишился графств, расположенных между ними и придававших его власти опасную концентрацию. Король Генрих не смог отразить опустошительный поход Болеслава до Эльбы летом 1003 года. Его контрудар весной 2004 года не удался. Болотистая местность на верхней Шпре и Эльстере была проходимой разве что для лягушек, а военная кампания возможной только осенью, когда войска могли, собирая урожай, сами обеспечивать себя продовольствием. Осенью 1004 года после ложной атаки с севера у Штрелы королю удалось вторгнуться в Богемию с севера через Рудные горы и посадить на престол Яромира, брата Болеслава. На обратном пути была вновь отвоевана Земля мильценов (мильчан) с Баутценом, которая получила собственного маркграфа в лице Германа, сына Эккехарда. Поход следующего, 1005 года, который после переправы через Одер возле Кроссена достиг Познани, закончил первую фазу польской войны Генриха «assumpta non bona расе» («приняв нехороший мир»). Условия его нам неизвестны: Богемия, Земля мильценов и Лаузиц, неукрепленные и заселенные только славянами, были сомнительным приобретением, однако имели ценность как единственный безлесый стратегический плацдарм на востоке. Болеслав обязан был возместить причиненный ущерб. Во время этого похода не состоялось ни одного открытого полевого сражения: на незнакомой, непроходимой местности они были чреваты для немцев большими потерями. Их нежелание вступать в бой с поляками, которых они никак не рассматривали в качестве врагов, становилось все отчетливее: область будущего миссионерства была опустошена, получить трофеи не представлялось возможным. Лютичи из-за своего опоздания расстроили надежду на верное уничтожение польской армии, прочного союзника Генрих в их лице не обрел. Впоследствии в предостережение лютичам была снова возведена крепость Арнебург, и Генрих принудил их к частым сборам в Вербене на Эльбе.
