"Фейеноорд" был основан предпринимателем в области горнодобывающей промышленности К.Р.Кибоомом. Звездой команды в довоенные годы был левый полузащитник Пак Ван Хеел, который в составе сборной Голландии дважды участвовал в чемпионатах мира 1934 и 1938 гг. и рекорд которого для Голландии (64 игры за сборную) держался еще много лет. Послевоенные годы были не самыми удачными для "Фейеноорда", но все изменилось в конце 1950-х гг., когда в Голландии распространился профессионализм. Для клуба начался период великих свершений в пределах страны: за 13 лет "Фейеноорд" шесть раз становился чемпионом Голландии, а в 1965 и 1969 гг. сделал "золотой дубль", выиграв чемпионат и кубок. За клуб играли такие звезды, как вратарь Эдди Питерс-Граафланд, купленный у "Аякса" за рекордную на то время сумму 20 000 фунтов; полузащитники Райнер Крайермаат, Ханс Краай и Йан Клаасенс и звезда первой величины левый крайний нападающий Кун Мулейн. Мулейн вместе со шведским бомбардиром Уве Киндваллом и мощным полузащитником Вимом Ван Ханегемом составляли ядро команды, которая в 1970 г. взяла Кубок европейских чемпионов, обыграв в Милане "Селтик" (в дополнительное время). Тренером клуба в то время был Эрнст Хаппель, бывший игрок сборной Австрии. Таким образом, именно "Фейеноорд" (а не именитый "Аякс") стал первым голландским клубом, завоевавшим престижнейший европейский трофей. И на этом роттердамский клуб не остановился. В финале Межконтинентального кубка он обыграл "Эстудиантес де Ла Плата" из Аргентины.

В 1974 г. "Фейеноорд" добавил к своим трофеям и Кубок УЕФА (в финале игру в центре поля вновь сделал Ван Ханегем). Однако впоследствии роттердамский клуб сдал позиции в голландском футболе. Из-за финансовых трудностей пришлось распродать лучших игроков, и в том числе Рууда Гуллита, которого "Фейеноорд" открыл в "Хаарлеме". Гуллита продали в ПСВ "Эйндховен", а позднее он перешел в "Милан". И только с приходом главного тренера Вима Янсена - бывшего игрока "Фейеноорда", входившего в сборную Голландии на чемпионате мира 1974 г., "Фейеноорд" сумел сплотиться заново и в 1993 г. стал чемпионом страны.