В качестве рядового Нильсен начал свою карьеру в первом батальоне Королевских фузилеров (лондонский полк), в Оснабруке, Германия. Командиром подразделения был лейтенант-полковник Тейлор. Он принял эту работу вместе с сержантом-квартирмейстером «Барсуком» Мэйтландом, приятным в общении веселым человеком с серьезной зависимостью от алкоголя. Сержантом-поваром был Томми Ибрагим, а коллегами и друзьями Нильсена в то время стали Джиджер Уотсон, Мики Дьюк, Боб Пирс, Дамбо Хоувит и Падди Аэрн. Командиром роты был майор Деннис. Это время для него было не менее счастливым – продолжение уютного товарищества в Олдершоте, время от времени прерываемое военными учениями. В Оснабруке Деннис также впервые начал пить. «Мы усердно пьянствовали: за два года службы мы не провели трезвыми ни ночи». Некоторые его приятели замечали, что Нильсен пьет больше других. Он ненадолго вернулся в Олдершот, чтобы сдать экзамен по общественному питанию уровня B1, а затем отправился служить со своей бригадой в Норвегию.
Счастье этих лет портила только одна серьезная проблема, беспокоившая его с каждым годом все больше. Еще в Олдершоте он начал понимать, что его влечет к другим парням, и это влечение необходимо было скрывать. Подавление своей сексуальности несло с собой сопутствующее чувство вины: раз желания следует скрывать, значит, они неправильные. Он считал себя бисексуалом, а не гомосексуалом, и, поскольку его никак нельзя было назвать женственным, притворство давалось относительно легко. Он тщательно следил, чтобы никогда даже случайно не упоминать о своей ориентации, и не объявлял о ней открыто, но его мучило неловкое подозрение, что его «ненормальность» всем очевидна. «Я никогда не принимал душ, только ванную. Я всегда боялся, что выгляжу без одежды не так, как остальные, и что внешняя нагота обнажит так же и мои потаенные мысли». Учитывая, что спал он в бараке с двадцатью другими парнями, облегчение он находил только в мастурбации в ванной в одиночестве.
В Оснабруке искушений для молодого человека стало больше, а значит, ему приходилось сдерживаться еще сильнее. Когда он приходил по вечерам пьяным, его наверняка часто раздевали и бросали в кровать его товарищи, и он то же самое делал для них. Никакого сексуального контакта не происходило. Если в их компании кто-то и обсуждал людей «нетрадиционной ориентации», то исключительно как предмет шуток и презрения. Деннис Нильсен осуждал это так же рьяно, как и его товарищи. Все это время он знал, что обманывает друзей и что его настоящее «я» задавлено этим притворством. Стресс от необходимости поддерживать обман постепенно начал накапливаться, хотя он этого не признавал.
В 1967 году, когда ему исполнилось двадцать один, Нильсена перевели в Аден, где расположилась охранно-полицейская служба, ответственная за заключенных террористов в тюрьме Аль-Мансура. Британцы вели отчаянную войну против арабских террористов, ведомых ненавистью и не заботящихся о собственном выживании. Тюрьма была настоящей крепостью, с тяжелыми воротами и обзорными вышками с автоматами, и часто подвергалась нападениям мятежников, так что вид усеивающих сельскую местность мертвых тел был обычным делом. Некоторые солдаты, попадавшие в засаду по пути к баракам, погибали или были изувечены, другим, достаточно глупым, чтобы развлекаться с местными проститутками, перерезали горло в процессе. В атмосфере иссушающего зноя и опасности это был тяжелый опыт. Добираясь до Аль-Мансуры через переполненные террористами земли, Деннис Нильсен сильно рисковал, приехав в тюрьму в кузове арабского грузовика с овощами. А когда он пил в баре «Оазис», один случай чуть не стоил ему жизни.