Группа сыграла кавер на песню This Will Be Our Year группы Zombies для Future Soundtrack for America, политического альбома, выпущенного лейблом Barsuk Records осенью 2004 года. Вокалист Дэмиен Кулаш стал немного политически активным во время выборов и написал книгу-инструкцию «How Your Band Can Fire Bush», надеясь что группы помогут сбросить Президента Джорджа Буша.

В 2007 году OK Go написали песню для футбольной команды Chicago Fire S.C.. Песня была вывешена на официальном сайте команды для бесплатного скачивания. В том же году OK Go записали кавер на песню Gigantic группы Pixies для альбома Dig For Fire — a tribute to PIXIES лейбла American Laundromat Records.

Слава, заслуженная клипами

Второй альбом под названием «Oh No» был записан в Мальмё, Швеция, и продюсирован Тором Йохансоном (он также продюсировал The Cardigans, Franz Ferdinand) осенью 2004 года. После записи, в 2005 году, Энди Дункан покинул группу, на замену ему пришёл Энди Росс. Альбом вышел в августе 2005 года.

Альбом Oh No заработал популярность благодаря клипу на песню A Million Ways, который стал заразительным Интернет-мемом осенью 2005 года. Супер-низкобюджетный клип изображал группу на их заднем дворе, исполняющую танец, поставленный сестрой Кулаша Триш Си. Камера была одолжена у знакомого, клип был снят за 10 долларов и выпущен, скорее всего, без знания или разрешения их лейбла Capitol Records. К августу 2006 года клип стал самым скачиваемым видео — больше 9 миллионов скачиваний. Группа выступила с этим танцем вживую на британской телевизионной передаче Soccer AM.

Необычный клип на песню A Million Ways — не первый для группы. Предыдущие оригинальные видео с OK Go включают их видеоинструкцию по настольному теннису и Федеральная правда музыкальных проектов. Они также выступали с танцем на песню C-C-C-Cinamon Lips после выхода их первого альбома. 31 июля 2006 года группа выпустила клип на песню Here It Goes Again, который изображал тщательно отработанный танец на беговых дорожках, также поставленный Триш Си. Этот клип просмотрели больше миллиона людей на сайте YouTube в первые 6 дней. До конца декабря 2008 года видео просмотрели больше 42 миллионов раз, что поставило его на 29 место среди самых просматриваемых видео и на 20 место среди самых просматриваемых клипов, а также на 6-е место среди видео, больше всего добавляемого в любимые, и 2-е среди клипов, больше всего добавляемых в любимые, на YouTube. Группа работала как с всемирно известными, так и с не очень знаменитыми режиссёрами, включая Фрэнсиса Лоуренса, Оливье Гондри (брата Михеля Гондри), Брайана Л. Перкинса, Скотта Кейнера И Тодда Салливана. 23 августа 2006 года Дэмиен Кулаш появился на The Colbert Report, чтобы поговорить о необычайной популярности A Million Ways и Here It Goes Again. Последнее видео получило награду YouTube как Самое Креативное в 2006 году. МС Common ссылается на видео в своей песне Drivin' Me Wild («She was the type to watch Oprah and the Today Show, be on the treadmill, uh, like 'OK Go'»).

В танцевальных клипах OK Go их басист Тим Нордвинд шевелит губами вместо вокалиста Дэмиена Кулаша, подражая танцу на песню C-C-C-Cinnamon Lips, которую поет Тим. 31 августа 2006 года OK Go выступили на MTV Video Music Awards с танцем на песню Here It Goes Again. С пор этого выступления продажи альбома и сингла увеличились, особенно на iTunes Music Store, где сингл достиг 11 места, а альбом — 2-го. 7 ноября 2006 года OK Go выпустили ограниченный тираж CD/DVD версии альбома Oh No. DVD включает их клипы, видео 180 фанов, исполняющих танец A Million Ways для соревнования YouTube и видео их репетиций танца Here It Goes Again.

В мае 2006 года они гастролировали с группой Panic at the Disco, в сентябре они были в Великобритании, поддерживая Motion City Soundtrack и продолжили тур по США в поддержку Snow Patrol до весны 2007 года.