В марте 1935 года Гитлер в одностороннем порядке денонсировал Версальский договор, и программа Редера по строительству флота начала осуществляться с полной силой. 18 июня 1935 года в Лондоне особый посланник рейха Иоахим фон Риббентроп подписал англо-германское военно-морское соглашение, в соответствии с которым Германия ограничивала общий тоннаж своих надводных сил до 35 процентов по отношению к надводным силам Объединенного Королевства. При этом количество субмарин не ограничивалось, и Германия могла иметь их столько, сколько было необходимо для сохранения паритета. Гитлер и Редер были в восторге, так как казалось, что соглашение исключает Великобританию из числа противников рейха. Адмирал даже запретил офицерам ОКМ (Obercommando der Kriegsmarine — главное командование ВМФ) любое упоминание о возможной войне с «туманным Альбионом» даже в условных штабных разработках. Еще 2 февраля 1933 года Гитлер сказал Редеру, что желает мирного сосуществования с Британией, а тот продолжал упрямо верить фюреру, исключая любые другие варианты развития событий, и сохранял этот нереалистичный подход к делу вплоть до мая 1938 года.
Создание военно-морского флота — очень трудная задача. В гораздо большей степени, чем сухопутная армия, флот строится в расчете на определенного противника. Гитлер приказал Редеру организовать Кригсмарине по подобию французского или советского флотов. Таким образом, СССР и Франция были объявлены наиболее вероятными противниками рейха. Ни Гитлер, «и Редер не хотели воевать с Великобританией, поэтому они убедили себя в том, что войны с ней не будет. Ни одному из них не пришло в голову, что даже в случае небольшой провокации Лондон может объявить войну Германии, так же, как сделал это в 1914 году.
Медовый месяц в отношениях Редера и Гитлера продолжался. В 1935 году титул Редера изменился. Он стал именоваться главнокомандующим Кригсмарине. 20 апреля 1936 года Гитлер, по случаю своего 47-летия, пожаловал Редеру звание генерал-адмирала, а в 1937 роду поборник морали стал почетным членом НСДАП. А тем временем, в 1936 году, началось строительство гигантских линкоров: «Бисмарк» водоизмещением 41 700 тонн и «Тирпитц» — 42 900. В последующие два года со стапелей сошли линкоры «Шарнхорст» и «Гнейзенау», а также легкие крейсеры «Лейпциг» и «Нюрнберг». Несколько позже за ними последовали тяжелые крейсеры «Хиппер» и «Блюхер». В этот же период строилось большое количество эсминцев и субмарин. Была создана 1-я подводная флотилия под командованием капитана цур зее Карла Деница.
Первые трещинки в отношениях между Редером и руководством рейха появились в 1938 году.[195] Еще в январе Гитлер выговорил адмиралу за нерасторопность, на что Редер с несвойственной ему едкостью заметил, что его программа строительства флота весьма успешно соревнуется с программой фюрера по строительству важных государственных объектов, таких, как мюнхенский метрополитен, огромные заводы «Фольксваген», сеть автобанов, а так же реконструкция Берлина и Гамбурга. В результате судоверфи испытывали недостаток в квалифицированных сварщиках и монтажниках, в материалах. Гитлер на намек не прореагировал, но потребовал увеличить темпы производства кораблей, спустить на воду «Бисмарк» и «Тирпитц» уже в начале 1940 года, разработать канонерскую подводную лодку и запустить в массовое производство субмарины типа VII. По указанию Редера, SKL (Seekriegsleitung — главный штаб ВМФ) ответил, что следует немедленно заморозить все военные проекты и высвободить рабочую силу для военного производства. Но фюрер ответил категорическим отказом. Программа строительства флота все больше и больше отставала от сроков, намеченных Гитлером.
Особенно ухудшал ситуацию тот факт, что руководство 4-летним экономическим планом, а значит, и распределение промышленных ресурсов, было сосредоточено в руках рейхсмаршала Германа Геринга Он и адмирал-пуританин презирали и ненавидели друг друга. Редер ненавидел Геринга за то, что тот свел на нет все его попытки создать морскую авиацию, и за то, что «толстый Герман» сыграл весьма неприглядную роль в деле Бломберга-Фрича. Геринг же, со своей стороны, подрывал репутацию Редера в ставке Гитлера, ставя под сомнение его политические взгляды, обращая внимание фюрера на то, что адмирал подозрительно часто ходит в церковь, и давая искаженную информацию о положении дел на флоте. Редер наблюдал, как хиреет и чахнет его программа, но особо на этот счет не беспокоился, ведь фюрер сказал, что флот понадобится не ранее 1944 года. Генерал-адмирал верил Гитлеру и действовал соответственно.