Rozłąka z rodziną nie była jedynym problemem. Niełatwe było także przetrwanie w Nowym Jorku. Wraz z przyjacielem wynajmował maleńkie mieszkanie, w którym panowała ciasnota i nieznośny upał. Aby zarobić pieniądze, malował dom u polskiego architekta. Ten załatwił mu pracę w biurze architektonicznym. Później Wolski został asystentem operatorów w BBC. W międzyczasie poznał kilkoro studentów wydziału filmowego Columbia University. Zaczął realizować z nimi drobne projekty filmowe, dzięki czemu mógł mieszkać w akademiku. Młodym adeptom filmowej sztuki imponował znajomością rzemiosła. Powoli zdobywał uznanie. I podejmował nowe wyzwania.
Choćby teledyski. Pracował przy ponad 100 wideoklipach, zdobywając w tej branży ogromne uznanie. Tworzył filmy dla Dawida Bowie i Eminema, Keitha Richardsa i Boba Dylana, Eltona Johna i Aerosmith. Za swoje teledyski otrzymał trzy nominacje do MTV Music Awards. Sukces na polu wideoklipów otworzył mu także drzwi do świata reklamy. Ale Wolski wciąż marzył o kinie.
I niedługo zaczął je tworzyć. W 1993 roku nakręcił "Krwawego Romeo", a niedługo później przyszła lawina propozycji. Pierwszą, bardzo ważną w karierze Wolskiego, złożył mu jego znajomy od teledysków – Alex Proyas przymieszał się do realizacji "Kruka" i chciał, by to Wolski stanął za kamerą. Wolski wyzwanie podjął i zaproponował bardzo odważną filmową formę. Jego zdjęcia różniły się od Hollywoodzkiej średniej – były mroczne, niepokojące i ciemne. W rozmowie z Arturem Zaborskim reżyser wspominał:
Na początku pracowałem z Davidem Fincherem, potem z Alexem Proyasem. Wytworzyła się między nami rywalizacja o to, kto wyprodukuje ciemniejszy film. Kiedy zrealizowałem zdjęcia do "Kruka", Fincher powiedział tylko: "No… dosyć ciemno". Kiedy on skończył pracę nad filmem "Siedem", zadzwoniłem i powiedziałem: "Wygrałeś". Trzeba było przeciwstawić się tradycyjnym sposobom oświetlania filmów i myśmy to robili.
