Castellanos Moya nació en Tegucigalpa, Honduras, país de donde era su madre, pero a los cuatro años de edad la familia se mudó a El Salvador, patria de su padre. Allí realizó sus estudios de primaria y secundaria en el marista Liceo Salvadoreño de la capital y luego ingresó a estudiar literatura en la Universidad de El Salvador, pero en 1979 los abandonó y partió al extranjero, primero a la York University de Toronto, en Canadá y, después, a Costa Rica (1980) y México (1981-1992). En México, trabajó como periodista en la Agencia Salvadoreña de Prensa (Salpress) en los tiempos de la guerra civil de El Salvador (país al que regresó por un breve periodo en 1991 con el proyecto fallido de iniciar una revista) y fue redactor de los diarios El día y Excelsior, además de corresponsal del periódico hispano La Opinión de Los Ángeles, California. Fue durante su estancia en ese país que escribió su primera novela, La diáspora, que en 1988 ganó el premio otorgado por la Universidad Centroamericana "José Simeón Cañas". En 1992 vuelve nuevamente El Salvador, pero en 1999 se traslada a España: después de la publicación de su novela El Asco: Thomas Bernhard en San Salvador (1997), su madre recibió amenazas de muerte dirigidas hacia Castellanos debido al contenido con el que trata algunos temas sensibles;​ en 2001 vuelve a residir en Ciudad de México. Entre 2004 y 2006 vivió en Fráncfort, por la invitación del programa Cities of Asylum de dicha ciudad y durante 2009 fue investigador invitado en la Universidad de Tokio. Reside en Estados Unidos, donde enseña en la Universidad de Iowa y es un columnista regular para la revista Sampsonia Way Magazine. Ha sido distinguido con galardones importantes, como el Iberoamericano de Narrativa Manuel Rojas,4​ y ha sido miembro de jurados literarios, como del I Concurso Hispanoamericano de Cuento Gabriel García Márquez (2014)