Вероятно, маленькому Каю прочили карьеру в театре, ведь его мать Ода была актрисой, а отец Мартинус — режиссёром. Семья Нильсенов жила в Копенгагене, столице Дании; в конце девятнадцатого века Дания, как и вся Европа, обожала театры, так что нужды Нильсены не знали. Тем более, что мать блистала на сцене не только у мужа в Театре Дагмар, но и Королевском Датском театре. Но Кай предпочёл стать художником. Юношей он поехал в Париж, чтобы учиться сначала в Академии Жюлиана, затем в Академии Коларосси.
После Франции Нильсен поехал в Англию, родину художников-прерафаэлитов. Там он впервые получил заказ на иллюстрацию сказок. 24 цветных и 15 чёрно-белых рисунков авторства Нильсена украсили книгу «Пудра и кринолин. Волшебные сказки, пересказанные сэром Артуром Квиллер-Кучем». Картинки Нильсена - типичные рисунки в стиле ар нуво, они милы и утончённы, пропитаны духом 1913 года.
В том же году в рождественском издании газеты «Иллюстрированные лондонские новости» публикуются иллюстрации Нильсена к сказкам Шарля Перро: «Спящей красавице», «Коту в сапогах», «Золушке» и «Синей Бороде».
В 1914 году Нильсен иллюстрирует сборник норвежских народных сказок «К востоку от солнца и к западу от луны». Сказки не на шутку его вдохновляют, сквозь общеевропейское ар нуво проступает суровая краса скандинавского Севера. Книга вышла тиражом в 500 экземпляров, в обложке с золотым тиснением, с 25 цветными и 21 чёрном-белым рисунком. На аукционах сохранившиеся экземпляры стоят от 8000 долларов.
В том же году он создаёт три иллюстрации к рассказу о жизни Жанны д’Арк, который выйдет намного позже, в 1920. А пока художник изучает у местных коллег новую для себя технику рисования, темперой.
В 1917 Нильсен посещает США с собственной выставкой рисунков, после чего возвращается, наконец, на родину. В Копенгагене он работает над оформлением сцены Королевского Датского Театра и, параллельно, над иллюстрациями к новому переводу «1000 и 1 ночи». Всё это — на фоне раздирающей Европу Первой Мировой войны.
Пока Мария Кюри ездила по линии фронта, обучая военных врачей пользоваться передвижным рентгеновским аппаратом для осмотра раненных, датчане хранили нейтралитет — покой Нильсена ничем не нарушался. Иллюстрации к «1000 и 1 ночи» были опубликованы только после смерти художника. Вероятно, для начала двадцатого века они оказались слишком фривольными, чтобы увидеть свет: на них было полно обнажённых пери.
В 1924 году Нильсен берётся за иллюстрации сказок самого известного датского писателя, Ганса Христиана Андерсена. Годом позже — создаёт рисунки к очередному изданию сказок братьев Гримм. Затем художник берётся за книгу британки Ромер Уилсон — это сборник сказок народов мира. Славянские сказки там тоже есть. Русского читателя иллюстрации Нильсена могут сильно удивить — художник никогда не был в славянских странах и рисовал костюмы и персонажей очень вольно.
Тем временем и в его жизни произошла волшебная встреча. Кай женится на девушке по имени Улла, милой моднице из обеспеченной датской семьи, с которой проживёт всю свою жизнь, пока смерть не разлучит их. Возможно, она послужила моделью для некоторых из его героинь.
В 1939 году Нильсен резко меняет карьеру. Он переезжает с семьёй в Калифорнию, чтобы работать на Голливуд. Слава театров уходит в прошлое, будущее — за фильмами. Он сотрудничает с самим Уолтом Диснеем, участвуя в создании музыкального мультфильма «Фантазия». Он также создаёт концепт-арты для многих диснеевских работ, включая, конечно, мультфильм по сказкам Андерсена — который, увы, так и не увидел свет. Тем не менее, концепт-арты Нильсена лежали в архивах студии и пригодились при работе над мультиком про Ариэль, вышедшим в 1989 году. А Нильсен прекратил сотрудничество с Диснеем в 1941 году и вернулся домой.
С началом Второй Мировой войны мир сильно изменился. Ар нуво утратил своё очарование в глазах большей части человечества. Волшебные сказки уже не интересовали детей, им хотелось сказок о войне и победе. Нильсен вышел из моды. Он уехал в Лос-Анджелес и всю оставшуюся жизнь провёл в нищете, расписывая стены школ и церквей.
Кай умер в 1957 году, прожив довольно долгую жизнь — 71 год. Улла пережила его всего на год. Только со временем мир понял, что Кай Нильсен, наряду с Йоном Бауэром и Карлом Улофом Ларссоном — один из самых зачаровывающих художников Скандинавии.