A few years ago, if you were going to apply to join the Australian Defence Force, you already had to have applied for Australian Citizenship (according to the chaps at Defence Plaza, Sydney). This is for someone applying straight off the street with no military experience. Not sure what the situation is now though.