Yes, aluminum oxidizes almost instantaneously in a normal atmosphere. It is one of the most reactive metals, i.e. it forms oxides very readily. As others have mentioned, you can actually see the oxide surface sputter off when welding with AC. But there is an important principle behind this. The aluminum oxide on the surface has a melting temperature of about 3700 degrees F while the aluminum base metal has a melting temperature of about 1200 degrees F.
Most metals will form a thin oxide surface fairly quickly but this is not as much a problem with some of them. For example for steel (iron), the base metal melts around 2800 degrees F while the oxides (there is more than one type of oxide) melts around 2900 degrees F, i.e. there is not much of a difference. Yes, you want to remove "heavy" oxides (e.g. rust, which can be combination of oxides and/or hydrated oxides) but this has more to do with potential contamination problems and arc stability problems (the oxides are less conductive and prevent smooth running of the arc) than physically making a molten weld pool. For aluminum, in addition to the oxide "contamination" of the weld pool, part of the problem in establishing the molten weld pool is the large difference in the melting temperature of the oxide versus the base metal.
Note that there are also other important physical effects which make aluminum more difficult to weld, specifically very high thermal conductivity, high specific heat and low melting temperature. This combination means that it is hard to heat up the base metal (because of the high thermal conductivity and high specific heat) but once it does heat up, you are quickly at the molten stage (due to the low melting temperature). For us unpracticed welders, that is why we end up going from no molten pool to suddenly finding a big hole. :-) The surface oxide problem on aluminum makes it just that much more difficult because if the oxide is not removed (by the sputtering action of AC) then the surface does not melt easily and greatly inhibits "wetting" of the surface my the filler metal.
I apologize if this turned out to be more than you wanted to know.