Aunque nacido en Honduras, su familia era de El Salvador, país al que regresaron en la infancia del escritor.
Castellanos realizó sus estudios de primaria y secundaria en el marista Liceo Salvadoreño de San Salvador. En 1979 tuvo que abandonar la Universidad de El Salvador, donde cursaba Letras desde 1976: debido a la situación de convulsión social que vivía el país, se exilió en Toronto, Canadá. Se estableció en Costa Rica en 1980, pero al año siguiente se trasladó a México donde vivió hasta 1992. En este período que coincidió con la Guerra Civil de El Salvador, trabajó en la Agencia Salvadoreña de Prensa (Salpress).
Su primela novela "La diáspora", ganó el Premio Nacional de Novela 1988, de la Universidad Centroamericana "José Simeón Cañas". Durante su exilio en México, trabajó como redactor de los diarios "El día" y "Excelsior" de la Ciudad de México y como corresponsal del periódico hispano "La Opinión" de Los Ángeles, California. En 1992 regresó a El Salvador, pero en 1999 se trasladó a España y desde 2001 residó nuevamente en la Ciudad de México. Entre 2004 y 2006 vivió en Fráncfort, por la invitación del programa "Cities of Asylum" de dicha ciudad.
