Podobnie jak część pierwszą, drugą i trzecią również wyprodukował DJ Premier.
W wywiadzie dla portalu Complex DJ Premier przyznał, że wszystkie wokale do utworu zostały nagrane za pierwszym podejściem: „Nas patrzył jak robiłem ten beat od samego początku i napisał tę zwrotkę w tym studiu. Jeśli posłuchasz „N.Y. State of Mind” usłyszysz jak mówi: „nie wiem jak zacząć to gówno”, ponieważ dosłownie chwilę wcześniej skończył pisać tę zwrotkę. […] Nagrał to za pierwszym podejściem”Oryginalny cytat: „Nas watched me build the beat from scratch. And he wrote the verse in the studio. If you listen to ‘N.Y. State of Mind’ you’ll hear him going, ‘I don’t know how to start this shit,’ because he literally just wrote it. […] He did that in one take”..
Od swojego pierwszego wydania „N.Y. State of Mind” było wielokrotnie samplowane oraz reprodukowane przez wielu artystów takich jak Alicia Keys, Raekwon, Beastie Boys, jak i przez samego Nasa. Piosenka znalazła się na ścieżkach dźwiękowych do gier True Crime: New York City (2005) i Saints Row 2 (2008).