Батальон был сформирован из бывших членов Киевской походной группы (Буковинский курень). Его командиром был майор Пфаль, заместителем — гауптман Поль (оуновец Полевой). На первом этапе существования батальон был одет в литовскую униформу и словацкие каски, оружие было трофейным советским. Каждый солдат носил белую нарукавную повязку со своим порядковым номером (комбат имел Mb 1). Трезубцы и желто-синие повязки было приказано убрать с формы.
Боевая деятельность батальона началась неудачно. В конце февраля 1942 года в батальон пришло известие, что в лесах в 100 км севернее Коростеня у села Хабина советские парашютисты убили нескольких селян за отказ вступить в их отряд. Из батальона была выслана разведка — 1-я рота под командованием сотника Остапенко и двух немецких офицеров. Вооружение группы состояло из советских трехлинеек и одного автомата у немецкого офицера. Рота попала в засаду и была полностью разбита, погибли 1 немец и 3 украинца. Из батальона были высланы на помощь 2-я и 3-я роты под командованием Пфаля. Они же нашли и похоронили убитых. Возвратившись в Киев после столь неудачного начала, батальон занимался охраной артиллерийского парка и строевой подготовкой. В мае 1942 года в батальоне прошли очередные аресты националистов, в основном членов Буковинского куреня и галичан. После репрессий в батальоне стал явно ощущаться недостаток унтер-офицерских кадров, поэтому на эти должности немцы стали назначать бывших старшин РККА. Вместе с ликвидацией национального украинского подполья в батальон стали прибывать бывшие военнослужащие Красной армии и бывшие белогвардейцы-эмигранты. Командиром 3-й роты стал бывший капитан Императорской Русской армии Некрасов. В июле 1942-го в батальон прибыло пополнение из молодежи, которую первоначально планировалось отправить на работу в Германию. Тогда же на базе одной из рот батальона было начато формирование 118-го полицейского батальона. После окончания комплектования 115-го батальона его состав насчитывал 350 человек.
В августе 1942 года оба батальона были переброшены в Барановичскую область Белоруссии. Начались боевые действия против партизан, с переменным успехом для обеих сторон. Постепенно под действием советской пропаганды бывшие красноармейцы, влившиеся ранее в батальон, начали переходить на сторону партизан.
Летом 1943 года батальон получил стандартную немецкую униформу полевой полиции, с правом ношения трезубца на пилотках. На левом рукаве мундиров носилась шитообразная нашивка, разделенная по диагонали на желтую и синюю половины, офицерский состав имел на щитке вышитый трезубец.