프로이센 왕국의 육군대령이던 알프레드 크뤼거의 아들로 당시 프로이센 왕국령이던 스트라스부르(현재는 프랑스령)에서 태어난 발터 크뤼거는 프로이센 육군사관학교를 졸업 후 소위로 임관하여 제1차 세계 대전 때 제100경보병연대에 배속되었다. 종군 중 두 번의 부상으로 1급 철십자 훈장을 받은 크뤼거는 전후에도 군에 남아 발트 지역에서 의용군에 참가하기도 했다.
1933년에 아돌프 히틀러가 정권을 잡았을 때도 독일 국방군에 있었던 크뤼거는 1935년4월에 친위대 중령으로서 무장친위대의 전신인 친위대 특무부대 게르마니아 연대에 이적하였다. 동생인 프리드리히 크뤼거도 돌격대에서 친위대로 이적했다. 얼마 후 크뤼거는 바트 퇼츠의 친위대 사관학교 교관이 되었는데 1939년1월에 친위대 대령이 되어 1940년1월부터 10월까지 경찰부대 참모장교가 되었다.