New Starting Over fue fundada en Osaka en el 2002 por Doige (Takeharu Doi), Eiki (Eiki Matsui), Shun (Shunsuke Sasamura) y Peki (Takayuki Kitamura). No les tomó mucho tiempo en construir una sólida reputación viendo sus presentaciones en vivo alrededor de Osaka donde se volvieron populares y fueron los fundadores del "screaming kei" (alias "Screamo Japonés"). El cuarteto también descubrió que la internet era una excelente plataforma para auto-promocionarse, usando páginas como Audioleaf, MySpace y Purevolume.com para expandir su música más lejos.
A pesar de sus fans, les tomó como dos años adicionales hasta el lanzamiento de su primer mini álbum "sublimation", el 3 de marzo del 2004. Hasta que fue lanzado, ellos sólo tuvieron una aparición en un álbum omníbus titulado "Seriously Funny, Funnily Serious!!!", en el cual participaron artistas compañeros de géneros screamo y punk como Dom Dom Fire, NO GAIN y GOOD 4 NOTHING. Un año después (y otra simple aparición), ellos publicaron su primer álbum, titulado "Ending Story". Después de este álbum con diez pistas aparecieron en el evento famoso de "Independece-D", donde tomaron parte bandas de diferentes géneros . Notables invitados fueron Balzac, MUCC y Loudness, entre muchas otras.
En noticias recientes, la banda ha anunciado una gira nacional para el verano del 2006. Los fans se están anticipando para verlos en vivo, curiosos de ver qué son capaces de hacer. Es sólo cuestión de tiempo antes de ver qué podrán ofrecer NSO a todos en el futuro y sus sueños realizándose de tocar en ultramar.
Aunque bandas como Endzweck o Envy han estado alrededor, New Starting Over es considerada por ser la primer banda de "Screamo" japonés. Screamo es un género musical en el cual se evolucionó lo emo, más específicamente hardcore emo en los tempranos años de 1990. El género es caracterizadod por gritos de voces hardcore y rápidas guitarras armonizadas.
La banda está formada por cuatro miembros y el micrófono es compartido por los guitarristas Doige (Voz) y Eiki (Gritos). Musicalmente, ellos podrían ser descritos como "Ellegarden conoce Endzweck". Para los fans del género, NSO podría recordarles a las ciertas canciones de la banda post-hardcore Senses Fail.
