Клуб «Витория» основан в 1922 в городе Гимарайнш, в 40 км на северо-восток от Порту. В клубе имеются футбольная, баскетбольная и волейбольная секции. Более частое использование названия «Гимарайнш» объясняется наличием в Португалии еще одной «Витории» — из города Сетубал.

Гимарайнш ни разу за свою историю не выигрывал чемпионат или Кубок Португалии, но имеет крепкую репутацию благодаря тому, что играет в высшей лиге португальского футбола с 1941 с перерывом на сезон 2006/07, а также является неоднократным участником Кубка УЕФА.

Вылетев во второй дивизион, «Витория» некоторое врем шла там на 10-м месте, но благодаря изменению в руководстве и клуба и назначению на пост тренера Мануэла Кажуды клуб сумел вернуться на свой обычный уровень — в Примейру.

В первом после возвращения сезоне «Витория» даже выпрыглула на третье место, получив путевку в квалификацию Лиги чемпионов 2008/09. Там команда проиграла по сумме двух матчей «Базелю», вылетела в квалификацию Кубка УЕФА, где п противостоянии с «Портсмутом» дотянула до добавленного времени, но таки проиграла 2:4.