¿Es «antes que nada» o «antes que todo»?

Lo más adecuado es usar antes que nada. Aunque antes de todo es una expresión válida, es propia del registro coloquial. Son opciones más cultas y preferibles antes que nada y antes de nada.