De padres noruegos, Stordahl empezó su carrera como trompetista en orquestas de jazz que tocaban en salones de baile.