Nina Nastasia nació y creció en Hollywood, Los Ángeles, California y es de ascendencia calabresa, italiana e irlandesa.^[7]​ Siendo niña, estudió piano y, a menudo, escribía cuentos, pero ella ha declarado que no tenía intención de convertirse en músico profesional.^[2]​

Comenzó a escribir canciones en 1993,^[8]​ y publicó su primer álbum, Dogs, en 2000. Inicialmente, solo se imprimieron 1.500 copias del álbum, y ella misma hizo el envoltorio del álbum en su apartamento. Nastasia los vendió todos en sus conciertos y a finales de ese mismo año el álbum estaba agotado. El famoso DJ John Peel lo calificó de "asombroso" tras recibir una copia proporcionada por Steve Albini. Peel comenzó a reproducir canciones de él con frecuencia en su programa de radio en BBC Radio 1,^[2]​ lo que ayudó a que Nastasia ganara seguidores de culto.^[9]​

Nastasia ha publicado seis álbumes, uno de ellos en colaboración con Jim White. Su primer álbum, Dogs, fue lanzado en 2000 en Socialist Records. Sus álbumes posteriores, The Blackened Air (2002) y Run to Ruin (2003), los sacó en el sello independiente Touch and Go Records, que también relanzó Dogs en 2004, seguido de una gira nacional; En CMJ, la periodista musical Kara Zuaro reseñó un programa en vivo que promocionaba Run to Ruin así: "Nastasia se remonta a una época en la que la música de cámara se interpretaba como un pasatiempo para los músicos, en lugar de un deporte para espectadores de sangre azul. Cuando el público aplaude sus presentaciones en vivo, ella y su simpática orquesta de Nueva York, menos el cantante que se fue para unirse al circo, se vuelven para sonreírse mutuamente".

En 2006, On Leaving fue lanzado en Fat Cat Records. En 2007, Fat Cat lanzó un álbum en el que colaboró con Jim White titulado You Follow Me. Todos los álbumes de Nastasia hasta la fecha fueron grabados por Steve Albini, quien ha elogiado apasionadamente su música en varias entrevistas. Posteriormente, Nastasia grabó seis sesiones para el programa del difunto disc jockey de la BBC, John Peel.^[2]​ La última fue grabada con la ayuda del grupo de folklore tuvano Huun-Huur-Tu. Dos de las canciones de Nastasia se incluyeron en el Festive Fifty anual de Peel: "Ugly Face" (cuarto puesto en 2002) y "You, Her & Me" (puesto 13 en 2003).^[10]​

<i>What She Doesn't Know</i>, un sencillo de 7 pulgadas, que contenía el tema principal, junto con la canción "Your Red Nose" se publicó el 25 de febrero de 2008. Ambos temas fueron grabados por Steve Albini durante las sesiones de On Leaving. Nastasia ha calificado el sencillo como "un buen complemento para You Follow Me".^[11]​ Una gira en solitario por Estados Unidos y Europa coincidió con el lanzamiento. El 10 de mayo de 2010 publicó el sencillo Cry, Cry, a escala internacional y el 18 de mayo en los EE. UU. Su sexto álbum de estudio, Outlaster, le siguió el 7 de junio de 2010.

Nastasia desapareció de la escena pública durante varios años.^[4]​ En septiembre de 2017, actuó en la fiesta del vigésimo aniversario de Electrical Audio en The Hideout Block Party en Chicago, Illinois.^[12]​ El 14 de diciembre de 2018,^[13]​ publicó el sencillo "Handmade Card" que no pertenece al álbum.^[14]​ En octubre de 2020, Nastasia emitió un comunicado para sus fanáticos en Bandcamp que decía: "He estado ausente mucho tiempo, pero acabo de terminar de grabar un nuevo álbum con Steve Albini. Voy a estar trabajando duro durante los próximos meses para sacarles esas canciones y muchas más en un futuro cercano".^[15]​

En febrero de 2022, Nastasia firmó un contrato discográfico con Temporary Residence Limited, que reeditó digitalmente On Leaving, You Follow Me y Outlaster ese mismo mes.^[16]​ En abril de ese mismo año actuó como telonera de la gira de Mogwai por Estados Unidos.^[17]​ Su séptimo álbum de estudio, Riderless Horse, se relanzó el 22 de julio de 2022.^[18]​

Críticos y periodistas han destacado en la música de Nastasia la mezcla elementos de folk y americana, con matices góticos.^[4]​ Su música ha sido comparada con la de Tom Waits, Devendra Banhart, Neko Case y Cat Power. En sus canciones destacan la guitarra acústica, a menudo acompañada de varios arreglos de cuerdas, como violonchelo, violín y viola.^[19]​^[20]​

Nastasia ha declarado en varias entrevistas que sabe poco de historia musical y que originalmente no tenía intención de convertirse en músico.^[2]​ También ha comentado que es fanática de las películas, particularmente de las películas de terror.^[21]​

• Dogs (2000; relanzado en 2004).
• The Blackened Air (2002).
• Run to Ruin (2003).
• On Leaving (2006).
• You Follow Me (2007), colaboración con Jim White.
• Outlaster (2010.)
• Riderless Horse (2022)

• " What She Doesn't Know" (2008).
• "Cry, Cry, Baby" "Our Gang" (promoción) (2010).
• "Puedes tomarte tu tiempo" "One Turned In" (2010).
• "Handmade Card" (2018).
• "Just Stay in Bed" (2022).

• 2001 "I Will Never Marry", en el álbum recopilatorio Comes with a Smile, Volume 3 - Pretty Together.
• 2005 "The Matter (of Our Discussion)", en el álbum de Boom Bip Blue Eyed in the Red Room ( Lex).
• 2005 "Bird of Cuzco", canción de John Peel: A Tribute compilación (WEA).
• 2009 "Repulsión", en el álbum recopilatorio Blanco y Negro, regalado con el número 12 de Esopus.^[22]​
• 2010 "Outside the Haus Tambaran", "Sand Reflection" y "Final Call" del álbum de David Corter Didgeridoo Dimensions.^[23]​
• 2018 "The Poisoner" en el álbum Chasescene de Daniel Knox.^[24]​