«Русенборг» начинал под названием другого клуба. 19 мая 1917 года двенадцать молодых людей из района Русенборг в Тронхейме основали «Спортсклуббен Одд», взяв название и цвета клуба «Одд» (Гренланн), тогда лучшей команды Норвегии. До 1928 года им не разрешали играть в любительских матчах лиги, а название «Русенборг» клуб принял осенью того же года. Старая связь напомнила о себе в 1960 году, когда клуб вышел в финал Кубка и встретился именно с той командой, чью идентичность позаимствовал. После ничьей 3:3 «Русенборг» выиграл переигровку 3:2 у «Одда» и завоевал первый трофей, который к тому же принёс первое участие в турнире УЕФА. Прозвище клуба — Троиллонган («Дети троллей») — происходит из местного диалекта, а белые футболки и чёрные трусы клуб носил большую часть своей истории.
До чемпионского титула пришлось ждать дольше. Первый был завоёван в 1967 году в составе с Харальдом Сунде, Оддом Иверсеном и молодым Нильсом Арне Эггеном, а два следующих — до 1971 года. Затем последовал долгий период без трофеев, включавший последнее место в 1977 году, когда команда выиграла за сезон лишь один матч. Перелом наступил в 1985 году, когда «Русенборг» обыграл «Лиллестрём» в последнем матче сезона и выиграл чемпионат с отрывом в одно очко. Три года спустя Эгген вернулся на пост тренера, приведя «Мосс» к титулу 1987 года, и под его руководством клуб выиграл чемпионат в 1988 и 1990 годах. Его влияние на стиль и культуру клуба — главная причина последовавшего доминирования.
С 1992 по 2004 год «Русенборг» выиграл тринадцать чемпионских титулов подряд — серия, не имеющая аналогов в норвежском футболе. Всего у клуба рекордные 26 чемпионских титулов, а по числу Кубков Норвегии он делит рекорд — 12. Он также провёл больше матчей в турнирах УЕФА, чем любая другая норвежская команда. Выход в Лигу чемпионов в 1995 году обеспечил финансы клуба и сделал его самым богатым в стране с большим отрывом. В 1995–2007 годах он одиннадцать раз за тринадцать лет играл в групповом этапе. Клуб выработал собственную трансферную модель. Такие игроки, как Эйвинн Леонхардсен, Харальд Браттбакк, Вегард Хеггем и Стиг Инге Бьёрнебю, переходили в ведущие клубы за границей, а «Русенборг» продолжал опираться главным образом на норвежских футболистов.
Самый памятный вечер той эпохи пришёлся на Лигу чемпионов 1996/97. Клуб, казалось, шёл к раннему вылету, но, когда «Милан» терял ценные очки, судьбу группы решил последний матч на «Сан-Сиро». «Русенборг» выиграл там 2:1, выбил итальянцев и стал первым норвежским клубом в четвертьфинале турнира. Там он уступил по сумме двух матчей 1:3 «Ювентусу». Тренер Нильс Арне Эгген позднее назвал эту победу вехой в истории клуба. Это был один из двух случаев, когда «Русенборг» вышел из первого группового этапа. Другой пришёлся на сезон 1999/2000, когда клуб выиграл свою группу и обеспечил место во втором групповом этапе.
Домашние матчи клуб проводит на стадионе «Леркендал» с 1950-х годов. Арена открыта в 1947 году, «Русенборг» переехал туда в 1957 году, а в 1996 году и затем в 2000–2002 годах она была перестроена в современный стадион с сидячими местами. Он остаётся домом одной из самых успешных команд Скандинавии. В последние десятилетия клуб сталкивается в стране с более сильной конкуренцией, чем в годы доминирования, но по-прежнему играет в высшем дивизионе — Элитсерии, а его рекорд по числу титулов не повторила ни одна другая норвежская команда.