Nossal was born in Bad Ischl. He first grew up in the Austrian capital city of Vienna. After the Anschluss (Nazi Germany's annexation of Austria), he and his family moved to Australia. This was because, although not of Jewish faith, his father's grandparents were Jewish. This meant that Nossal was at risk of being sent to concentration camps due his Jewish background. Nossal was baptised, like his father, and is a Roman Catholic. He studied at the University of Sydney.