The properties of functional materials are intrinsically linked to their atomic structure. When going to the nanoscale, size-induced structural changes in atomic structure often occur, however these are rarely well-understood. Here, we systematically investigate the atomic structure of tungsten oxide nanoparticles as a function of the nanoparticle size and observe drastic changes when the particles are smaller than 5 nm, where the particles are amorphous. The tungsten oxide nanoparticles are synthesized by thermal decomposition of ammonium metatungstate hydrate in oleylamine and by varying the ammonium metatungstate hydrate concentration, the nanoparticle size, shape and structure can be controlled. At low concentrations, nanoparticles with a diameter of 2-4 nm form and adopt an amorphous structure that locally resembles the structure of polyoxometalate clusters. When the concentration is increased the nanoparticles become elongated and form nanocrystalline rods up to 50 nm in length. The study thus reveals a size-dependent amorphous structure when going to the nanoscale and provides further knowledge on how metal oxide crystal structures change at extreme length scales.