До начала съёмок в одном из фильмов Paramount, Фред Макмюррей успел сняться в главной мужской роли в мелодраме «Grand Old Girl» студии RKO Radio Pictures. Первым же его фильмом с Paramount Pictures стала мелодраматическая комедия 1935 года «The Gilded Lily». Партнёршей Фреда стала сама Клодетт Колбер, перед этим снявшаяся в фильме «Это случилось однажды ночью», за который ей будет присуждён «Оскар» через месяц после премьеры «The Gilded Lily». Следующим совместным фильмом МакМюррея и Колбер стала комедия «Невеста возвращается домой».

Всего же за первый год съёмок у Paramount Макмюррей снялся в шести фильмах. Его партнёршами, кроме Клодетт Колбер, были Кэтрин Хепберн, Кэрол Ломбард, Энн Шеридан и Мэдж Эванс.

Первым фильмом 1936 года для Фреда Макмюррея стала картина «Тропинка одинокой сосны». Это был первый цветной фильм, полностью снятый не в студии. Макмюррей играет инженера, приехавшего строить железную дорогу в горах Кентукки. Вместе с этим, он пытается образумить два враждующих клана, много лет живущих по законам мести. Одну из главных ролей в фильме сыграл Генри Фонда. Затем последовали «Принцесса пересекает океан», «Техасские рейнджеры» и «Тринадцать часов самолётом». Среди ролей актёра в 1930-е следует отметить мелодраму «Приглашение к счастью» с Ирен Данн, мюзикл «Sing You Sinners», где Фред Макмюррей, Бинг Кросби и Дональд О’Коннор играют трёх братьев с совершенно различными характерами, драму «Exclusive» с ярко блеснувшей звездой 30-х Фрэнсис Фармер и комедию «Чистосердечное признание», где Макмюррей сыграл адвоката, совершенно не умеющего лгать, который вынужден защищать в суде собственную супругу (её сыграла Кэрол Ломбард).

В 1940-е Фред Макмюррей сыграл свои самые известные роли. Среди них командир эскадрильи Джо Блейк из фильма «Пикирующий бомбардировщик», повествующего о работе военно-морских медиков и летчиков США, Кори Макбейн из мелодрамы «Так хочет леди», где снялась и Марлен Дитрих, профессор Ричард Майлз в триллере «Вне подозрений» и, конечно же, Уолтер Нефф из «Двойной страховки».

Фильм-нуар «Двойная страховка» режиссёра Билли Уайлдера стала одной из самых нашумевших картин 1940-х годов и принесла бешеную популярность актёрам. Фильм выдвигался на «Оскар» в семи номинациях, но не выиграл ни одной. Само его название носило провокационный характер. «Двойная страховка» — это традиционный для страховых полисов тех лет пункт, гарантирующий выплаты в двойном размере, если застрахованный погибает от маловероятного несчастного случая.

В 1945 году актёр сыграл главную роль в мюзикле «Куда мы отсюда пойдем?». На съёмках он познакомился с девятнадцатилетней Джун Хэвер, которая через несколько лет станет его второй женой. Далее был успех комедийной картины «Яйцо и я» (1947), в этом фильме он снялся вместе с Клодет Колберт. Фильм был одним из крупнейших хитов года, а затембыл признан в составе 12 самых прибыльных фильмов 1940-х годов.

В 1950-х самым известным фильмом Макмюррея стал «Бунт на «Кейне»». Экранизация романа Германа Воука также заработала семь номинаций на «Оскар». Действие романа разворачивается на военном эсминце во время Второй мировой войны. Происходит беспрецедентный случай в истории флота Соединённых Штатов. Капитан судна устранён с поста в результате мятежа. Команда начала подозревать его в психическом расстройстве, он вынужден давать показания.