Existen diversas teorías sobre los orígenes del nombre Eilean Donan, que significa isla de Donan. Según la primera y más probable, el castillo debe su nombre a un santo irlandés del siglo VI, el obispo Donan, que viajó a Escocia en torno al año 580 d. C. En los alrededores del castillo hay varias iglesias consagradas al santo, por lo que es posible que formase una comunidad cristiana en la isla a finales del siglo VII.
La primera edificación fortificada se construyó a principios del siglo XIII con el fin de proteger el territorio de Kintail. Desde el año 800 y hasta el 1266, gran parte del norte de Escocia y las Hébridas Exteriores fueron víctimas de la invasión y la colonización vikingas, y los castillos eran una pieza esencial para detener su avance. Desde mediados del siglo XIII, la zona formó parte del llamado reino del mar de los Señores de las islas, una serie de gobernantes que se constituyeron en potencia naval. Los cabecillas de los distintos clanes, enfrentados entre sí, medían su poder por su número de vasallos y galeras, denominadas birlinns, y Eilean Donan constituía el perfecto enclave defensivo.
Las dimensiones del castillo han variado a lo largo de los siglos. En la época medieval, es probable que las torres y los muros llegaran a ocupar casi toda la isla, con la torre del homenaje en el punto más alto. A finales del siglo XIV, el castillo pasó a ocupar tan sólo un quinto de la extensión original. Aunque se desconocen las causas, es posible que se debiese a la imposibilidad de mantener un destacamento de la envergadura necesaria para defenderlo. En el siglo XVI, el muro oriental se consolidó con un hornabeque con espacio para los nuevos cañones.
Eilean Donan también desempeñó un papel importante en los levantamientos jacobitas de los siglos XVII y XVIII, que dejaron el castillo en ruinas.
En 1719, un destacamento español de cuarenta y seis soldados que apoyaban la causa jacobita tomó el castillo y, mientras esperaba a recibir más armamento y un cañón procedentes de España, construyó un polvorín. Pero los rumores del levantamiento llegaron a oídos del gobierno inglés, que envío tres fragatas armadas (The Flamborough, The Worcester y The Enterprise) para acallarlo. Durante tres días, las fragatas bombardearon el castillo sin demasiado éxito debido al grosor de sus muros, de cuatro metros y medio en algunos lugares. Finalmente, el capitán del Enterprise, Herdman, envió a tierra a sus hombres y logró derrotar a los soldados españoles. Tras la rendición, las tropas del gobierno hallaron el polvorín y utilizaron los 343 barriles de pólvora que albergaba para volar las zonas que no habían sucumbido al bombardeo.
Durante casi dos siglos, el castillo quedó reducido a ruinas y a merced de los elementos, hasta que el teniente coronel John MacRae-Gilstrap compró la isla en 1911 y decidió devolver a Eilean Donan su antiguo esplendor. Durante dos décadas, su aparejador, Farquhar Macrae, le ayudó a reconstruirlo, guiándose por los planos de las etapas anteriores. Las obras concluyeron en julio de 1932.
