Rođen je 22. rujna 1957. godine u malom gradu Warracknabeal u državi Viktorija u Australiji. Nickov otac Colin radio je kao profesor engleskog jezika i administrator. Volio je književnost, baš kao i Nickova majka Down, koja je radila kao knjižničarka. Odgojen kao pripadnik anglikanske crkve, Cave je odmalena pjevao u crkvenom zboru u katedrali. Kako je rastao, počeo je prezirati način života u malim gradovima u Australiji, pa je često radio probleme u školi i bio u sukobu da profesorima. Zbog toga su ga 1970. godine njegovi roditelji poslali u internat srednje škole u Melburnu.

Nick je imao 19 godina kada mu je otac poginuo u prometnoj nesreći. Njegovoj majci je ova tragična vijest priopćena baš u trenutku kada je plaćala kauciju za Nicka, koji je bio u pritvoru zbog provale i krađe.

Po završetku srednje škole Nick Cave je počeo studirati slikarstvo, ali je odustao godinu dana kasnije kako bi se posvetio glazbi.