Murphy próbował zaciągnąć się do wojska w rodzinnym Teksasie, ale został odrzucony przez komisję, ponieważ był zbyt młody. Dzięki pisemnemu oświadczeniu swojej starszej siostry Corinne, w którym stwierdziła pełnoletniość brata, podając fałszywą datę jego urodzenia, ponownie zgłosił się do komisji poborowej i tym razem został przyjęty. Po przejściu podstawowego przeszkolenia wojskowego został wysłany do Tunezji, a następnie na Sycylię i do Europy Zachodniej, gdzie walczył w dziewięciu dużych kampaniach i w ciągu trzech lat awansował z rangi szeregowego do podporucznika.
Dla wielu osób powodem odrzucenia Murphy’ego przez komisję było to, że nie pasował on do „wizerunku” bohatera wojennego. Był niewielkim, kruchym, nieśmiałym młodym człowiekiem o łagodnym głosie, którego chłopięcy wygląd (coś, czego nigdy nie stracił przez całe życie, zawsze wyglądał dużo młodziej niż w rzeczywistości) często szokował ludzi, kiedy ci dowiadywali się, że na przykład, w czasie bitwy w kotle kolmarskim w styczniu 1945 r.