W obozie tym uczestniczył w pierwszych próbach użycia cyklonu B do masowego zabójstwa radzieckich jeńców wojennych. Następnie służył w Majdanku w latach 1941–1942Ernst Klee: Das Personenlexikon zum Dritten Reich. Frankfurt am Main 2007, s. 631., gdzie w kwietniu 1942 został lekarzem głównym, zastępując zmarłego na tyfus Maxa Popierscha. Niedługo potem podjął kroki, aby odejść ze służby w obozie i pracować jako lekarz na froncie, jednak również zachorował na tyfus, z powikłaniami: zapaleniem płuc i zakrzepicą. Po początkowym leczeniu w lubelskim szpitalu SS trafił na rehabilitację do szpitala w Radebeulu, gdzie przebywał do sierpnia 1943.
Formalnie już od lutego 1943 został lekarzem garnizonowym w obozie koncentracyjnym Neuengamme. Wiązało się to z awansem na Hauptsturmführera. Oznaczało to oprócz fasadowego nadzorowania leczenia więźniów zwykłą służbę medyczną wobec załogi i stacjonujących żołnierzy. W obozie tym prowadzono doświadczenia polegające na zakażaniu gruźlicą. Heissmeyer prowadził te badania, mimo braku wiedzy bakteriologicznej, z przekonaniem, że charakter tej choroby ma w większej mierze wymiar rasowy niż zakaźny. Trzebinski sam nie brał udziału w badaniach, a według późniejszych zeznań uważał je za pozbawione wartości medycznej, wyznaczył natomiast do asystowania Heissmeyerowi lekarzy będących więźniami obozu.